Исследовательская работа на тему «Использование элементов математической логики при решении задач»

Департамент образования мэрии                                                     ФГБОУ ВПО «Тольяттинский

Городского округа Тольятти                                                            государственный университет»

ХХ городской Конгресс молодых исследователей

«Шаг в будущее»

Исследовательская работа на тему

«Использование элементов математической логики при решении задач»

Секция: Математика

Автор:

Судакова Татьяна Сергеевна,

ученица 10 «Б» класса МБУ гимназии № 77

г.о. Тольятти Самарской обл.

Научный руководитель:

Журавкова Любовь Васильевна,

учитель МБУ гимназии № 77

г.о. Тольятти Самарской обл.

Тольятти 2013

Введение

Логика – это Бог мыслящих.

Л. Фейхтвангер

Умение правильно рассуждать необходимо в любой области человеческой деятельности: науке и технике, юстиции и дипломатии, планировании экономики и  военном деле.  И это умение восходит к древнейшем временам, логика, т.е.  наука о том, какие формы рассуждений правильны, возникла лишь немногим более двух тысяч лет тому назад. Она была развита в VI в. до н.э. в работах великого древнегреческого философа Аристотеля, его учеников и последователей.

В какой-то момент математики задали вопрос: «В чем, собственно, состоит математика, математическая деятельность?» Простой ответ заключается в том, что математики доказывают теоремы, то есть выясняют некоторые истины о реальном мире и «идеальном математическом мире». Попытка ответить на вопрос что такое математическая теорема, математическая истина и что такое математическое утверждение истинно или доказуемо, это и сеть исходная точка математической логики. Мы должны в школе научиться анализировать, сравнивать, выделять главное, обобщать и систематизировать, доказывать и опровергать, определять и объяснять понятии, ставить и решать проблемы. Овладение этими методами и означает умение мыслить. В науке приходится путем рассуждений выводить разнообразные формулы, числовые закономерности, правила, доказывать теоремы. Например, в 1781 г. была открыта планета Уран.  Наблюдения показали, что движение этой планеты отличается от теоретически вычисленного движения.  Французский ученый Леверье (1811-1877гг.), логически рассуждая и выполнив довольно сложные вычисления, определил влияние на Уран другой планеты и указал место ее нахождения. В 1846 г. астроном Галле подтвердил существование планеты, которая была названа Нептун. При этом они использовали логику математических рассуждений и вычислений.

2

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

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

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

Задачи:

1. Проанализировать литературу о сущности и возникновении математической логики.

2. Изучить элементы математической логики.

3. Подобрать и решить задачи с элементами математической логики.

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

1.  Из истории возникновения математической логики

Математическая логика тесно связана с логикой и обязана ей своим возникновением. Основы логики, науки о законах и формах человеческого мышления были заложены величайшим древнегреческим философом Аристотелем (384—322 гг. до н. э.), который в своих трактатах обстоятельно

исследовал терминологию логики, подробно разобрал теорию умозаключений  

3

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

В дальнейшем многие философы и математики развивали отдельные положения логики и иногда даже намечали контуры современного исчисления высказываний, но ближе всех к созданию математической логики подошел уже во второй половине XVII века выдающийся немецкий ученый Готфрид Вильгельм Лейбниц (1646 - 1716), указавший пути для перевода логики «из словесного царства, полного неопределенностей, в царство математики, где отношения между объектами или высказываниями определяются совершенно точно».  Лейбниц надеялся даже, что в будущем философы, вместо того чтобы бесплодно спорить, станут брать бумагу и вычислять, кто из них прав. При этом в своих работах Лейбниц затрагивал и двоичную систему счисления. Следует отметить, что идея использования  двух символов для кодирования  информации очень стара. Австралийские аборигены  считали двойками, некоторые племена охотников-сборщиков Новой Гвинеи и Южной Америки тоже пользовались двоичной системой счета. В некоторых африканских племенах передают сообщения с помощью барабанов в виде комбинаций звонких и глухих ударов. Знакомый всем пример двухсимвольного кодирования - азбука Морзе, где буквы алфавита представлены определенными сочетаниями точек и тире. После Лейбница исследования в этой области  вели многие выдающиеся ученые, однако настоящий успех пришел здесь к  английскому математику-самоучке Джорджу Булю (1815—1864), его

целеустремленность не знала границ.

4

Материальное положение родителей Джорджа (отец которого был сапожным мастером) позволило ему окончить лишь начальную школу для бедняков. Спустя какое-то время Буль, сменив несколько профессий, открыл маленькую школу, где сам преподавал. Он много времени уделял самообразованию и вскоре увлекся идеями символической логики. В 1847 году Буль опубликовал статью «Математический анализ логики, или Опыт исчисления дедуктивных умозаключений», а в 1854 году появился главный его труд «Исследование законов мышления, на которых основаны математические теории логики и вероятностей». Буль изобрел своеобразную алгебру  - систему обозначений и правил, применимую ко всевозможным объектам, от чисел и букв до предложений. Пользуясь этой системой, он мог закодировать высказывания (утверждения, истинность или ложность которых требовалось доказать) с помощью символов своего языка, а затем манипулировать ими, подобно тому, как в математике манипулируют числами. Основными операциями булевой алгебры являются конъюнкция (И), дизъюнкция (ИЛИ) и отрицание (НЕ). Через некоторое время стало понятно, что система Буля хорошо подходит для  описания электрических переключательных схем. Ток в цепи может либо протекать, либо отсутствовать, подобно тому, как утверждение может быть либо истинным, либо ложным. А еще несколько десятилетий спустя, уже в XX столетии, ученые объединили созданный Джорджем Булем математический аппарат с двоичной системой счисления, заложив тем самым основы для разработки цифрового электронного компьютера.  Отдельные положения  работ Буля в той  или иной мере затрагивались и  до, и после него другими математиками и логиками. Однако сегодня в данной области именно труды Джорджа Буля причисляются к математической классике, а сам он по праву считается основателем математической логики и тем более важнейших ее разделов - алгебры логики (булевой алгебры) и алгебры  высказываний.

Большой вклад в развитие логики внесли и  русские ученые П.С.

Порецкий (1846-1907), И.И. Жегалкин (1869-1947).

5

В XX веке огромную роль в развитии математической логики сыграл

Д. Гильберт (1862-1943), предложивший программу формализации математики, связанную с разработкой оснований  самой математики. Наконец, в последние  десятилетия XX века бурное развитие математической логики было обусловлено развитием теории алгоритмов и алгоритмических языков, теории автоматов, теории графов (С.К. Клини, А. Черч, А.А Марков, П.С. Новиков и многие другие).  

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

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

2. Элементы логики высказываний

   Алгебра  логики (логика высказываний) - один из основных разделов

6

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

преобразованиях высказываний. 

Высказывание - это термин математической логики, которым

обозначается предложение какого-либо языка (естественного искусственного),

рассматриваемого лишь в связи с его истинностью.

Отличительным признаком любого высказывания является его свойство быть истинным или ложным.

Рассмотрим некоторый класс объектов и установим свойства этих объектов, а также отношения и операции над ними. Простые высказывания являются простейшим объектом логики высказываний. Рассмотрим несколько примеров простых высказываний:  «Некоторые свойства мышления не моделируются средствами современной кибернетики», «Верста больше километра», «Число 100 больше числа 10». В двузначной логике единственный способ оценки сводится к утверждению или отрицанию истинности высказывания. В такой логике есть смысл абстрагироваться от различий между суждением и высказыванием и рассматривать их как синонимы.

Используя простые высказывания, можно образовывать сложные, или составные, высказывания, в которые простые входят в качестве элементарных составляющих. Таким образом, в отличие от сложного, простое высказывание не поддается расчленению на высказывания.  В образовании сложных высказываний используются слова: и, или, тогда и только тогда, когда (в том и только в том случае), если …, то …, нет. Рассмотрим  несколько примеров сложных высказываний:

1) Если идет дождь, то солнце не светит.    2) Если ветер дует, то нет дождя.

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

истинности или ложности простых высказываний определить истинность или

7

ложность сложных высказываний. Среди сложных высказываний можно

выделить соединительные, разделительные, условные, эквивалентные и высказывания с внешним отрицанием.

Логические операции часто называют логическими связками, и для них используется система символических обозначений. Простые высказывания будем обозначать большими буквами A, B, C и т.д., и, если высказывание истинно, будем писать A=1, а если ложно, то A=0. Для булевых переменных, то есть переменных, которые принимают только два значения, называемые «истиной» (TRUE) и «ложью» (FALSE) и обозначаемые соответственно 1 и 0, определены следующие логические операции (здесь приведены различные обозначения, встречающиеся в литературе):

1) ¬ - означает логическое НЕ

2) &, и, AND – означает логическое И

3) +, или, OR – означает логическое ИЛИ

4) → - импликация

5) ↔, = - двойная импликация или эквиваленция

Операция отрицания (иногда называют операцией инверсии) является простейшей операцией логики высказываний. Если  А – истинное высказывание, то ¬А является ложным высказыванием, и наоборот, если А – ложно, то ¬А – истинно. Операция отрицания выражается словосочетанием «неверно, что» и определяется следующей таблицей истинности:

Операция конъюнкции (логического умножения). Соединение двух простых высказываний A и B в одно составное с помощью союза «и» называют логическим умножением или конъюнкцией, а результат операции —

логическим произведением.

8

Конъюнктивное (соединительное) высказывание АΛВ – это высказывание, в котором утверждается наличие двух ситуаций. Например, «солнце светит и нет дождя».  Операция конъюнкции определяется с помощью следующей таблицы истинности:

Таким образом, сложное высказывание АΛВ истинно в том и только в том случае, когда оба высказывания А и В являются истинными. Например, пусть высказывание А – число 100 делится на 5, а высказывание В – число 100 больше 5. Тогда сложное высказывание АΛВ будет истинным.

Операция дизъюнкции (логическое сложение), соответствующая союзу «или» имеет два различных значения. Следует различать исключающее «или» и неисключающее «или».  Логическая операция, соответствующая неисключающему «или» называется дизъюнкцией и обозначается  АVВ, а полученное составное высказывание — логической суммой.  Дизъюнкция определяется следующей таблицей истинности:

Таким образом, дизъюнкция (логическая сумма) АVВ ложна тогда и только тогда, когда оба высказывания ложны.

9

Например, пусть высказывание А – число 20 делится на 7, а В – число 20 больше 7, тогда сложное высказывание АVВ «число 20 делится на 7 или число 20 больше  7» будет истинным.  

Для высказывания, соответствующего исключающему «или», часто используется словосочетание «или…, или…» («либо…, либо…»). Ниже приведена таблица для дизъюнкции, соответствующей исключающему «или»:

Рассмотрим два примера дизъюнкции, соответствующей неисключающему «или» и исключающему «или»:        

1) «Володя вчера в шесть часов  вечера читал книгу или ехал  в автобусе на стадион». Союз  «или» использован в этом предложении  в неисключающем смысле — Володя мог читать и одновременное ехать в автобусе. Одно не исключает другого.

2) «Володя вчера наблюдал за ходом матча с западной или  восточной трибуны». Здесь союз  «или» имеет исключающий характер  — две описываемые ситуации исключают друг друга: нельзя наблюдать один и тот же матч одновременно с двух противоположных трибун.

Импликация (логическое следование) – это одна из самых важных операций логики высказываний. Эта операция соответствует обороту «если…, то…». По определению импликация   А→ В истинна всегда за исключением случая, когда А истинно, а В ложно. Таблица истинности для операции импликация имеет следующий вид:

10

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

а) если 2+3=6, то 2*2=4

б) если 2+3=6, то 2*2=5

Очень часто высказывание после слова «если» называется основанием, а после слова «то» следствием. Например, «если идет дождь, то земля мокрая». Здесь простое суждение «идет дождь» - основание, а следствие – «земля мокрая».

Эквиваленция.  Высказывание «А тогда и только тогда, когда В»

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

Таким образом, сложное высказывание А↔В – это высказывание, в котором утверждается одновременное наличие или отсутствие двух ситуаций.

11

Выражается, как правило, словосочетаниями «если и только если..., то…», «в том и только в том случае, когда…», «тогда и только тогда, когда…».

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

Используя основные логические операции, можно построить более сложные высказывания, например,

( АΛВ) V (АΛВ) V (¬АΛ¬С), (¬(АVВ) →С) = ¬А.

Указанные высказывания называются формулами алгебры высказываний А, В,…, знаков логических операций (¬,V, Λ, →, =), а также скобок.

12

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

3. Задачи и их решение

Задача 1. 

Решаем методом «здравых рассуждений».

Пять десятиклассников приехали из пяти различных городов Самарской области в Самару на областную олимпиаду по экономике. «Откуда вы, ребята?» – спросили их организаторы олимпиады.
Вот что ответил каждый из них.

    Андреев: «Я приехал из Тольятти, а Григорьев живет в Жигулевске».

    Борисов: «В Жигулевске живет Васильев. Я же прибыл из Октябрьска».

    Васильев:  «Я – из Тольятти, а Борисов – из Кинеля».

    Григорьев: «Я приехал из Жигулевска, а Данилов из Чапаевска».

    Данилов: «Да, я действительно из Чапаевска, Андреев же живет в Октябрьске».

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

Решение.

Рассмотрим первый возможный вариант.  Пусть первое утверждение Андреева верное, то есть он из Тольятти. Тогда Григорьев живет не в Жигулевске. Поэтому второе утверждение Данилова – ложное, значит, он из Чапаевска. Тогда первое утверждение Григорьева – ложно.

13

Так как Андреев из Тольятти, то первое утверждение Васильева ложно, поэтому Борисов – из Кинеля. Так как Григорьев не из Жигулевска, то остается, что он из Октябрьска, а Васильев – из Жигулевска.

Рассмотрим второй возможный вариант. Пусть у Андреева второе утверждение – правильное, тогда Григорьев приехал из Жигулевска. Значит, Данилов приехал не из Чапаевска, а Андреев не из Тольятти. Тогда у Борисова первое утверждение ложное (в Жигулевске живет Григорьев), следовательно, Борисов прибыл из Октябрьска. Поэтому Андреев не из Октябрьска и получается, что Данилов – из Чапаевска. Получили противоречие: Данилов из Чапаевска и не из Чапаевска. Значит, второй вариант невозможен.

Ответ.    Андреев – из Тольятти, Борисов – из Кинеля, Васильев – из Жигулевска, Григорьев – из Октябрьска, Данилов – из Чапаевска.

Задача 2.

Решаем с помощью таблиц.

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

Из четырех офицеров – Александрова, Борисова, Васильева и Григорьева – два лейтенанта, один капитан и один майор. Александров и один из лейтенантов – танкисты, Борисов и капитан - артиллеристы, Александров младше по званию, чем Васильев. Определите род войск и воинское звание каждого из них.

Решение.

Составим  три таблицы и отразим в них условия задачи, заполнив соответствующие клетки цифрами 1 и 0 в зависимости от того, ложно или истинно соответствующее высказывание.

14

Используя данные задачи, поставим 1 на пересечении Борисов – артиллерист, Александров – танкист,  лейтенант – танкист, капитан – артиллерист. Тогда Борисов – не танкист и не капитан. Капитан не танкист. Александров – не артиллерист и не капитан. Поставим соответственно 0 на пересечении данных слов в таблицах. Тогда получим:

15

Александров не капитан и не майор (так как младше по званию, чем  Васильев), значит он лейтенант. Получается, что оба лейтенанта танкисты, а Борисов – артиллерист, значит он не лейтенант. Так как Борисов не лейтенант и не капитан, то он майор. Тогда Васильев – капитан, поэтому он – артиллерист. Григорьев, значит, лейтенант и танкист.

В результате постепенного заполнения получаем следующие таблицы:

Ответ:  Васильев и Борисов -  капитан и майор артиллерии, Александров и Григорьев – лейтенанты танковых войск.

Задачи на принцип Дирихле.

Принцип Дирихле выражает соотношение между двумя множествами.

16

Существует несколько формулировок этого принципа. Самой популярной является такая: «Если в n клетках сидит m зайцев, причем m>n, то хотя бы в одной клетке сидят по крайней мере два зайца». Доказывается принцип Дирихле методом от противного. Допустим, что в каждой клетке будет находиться не более одного зайца. Тогда в n клетках будет находиться не более n зайцев, что противоречит условию.

Существуют и другие формулировки принципа Дирихле.

Вот, например, обобщенный принцип Дирихле:
«Если в n клетках сидят m зайцев и m≥kn + 1, то в какой-то из клеток сидят, по крайней мере, k + 1 заяц».

Рассмотрим его применение на нашей задаче.

Задача 3.

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

Доказательство. Так как трое маркетологов вместе провели анализ  6 (1+2+3) товаров, то анализ оставшихся 29 товаров провели 7 маркетологов. Приняв товары за «зайцев», а маркетологов за «клетки», имеем 29 = 4*7 + 1. Тогда, по обобщенному принципу Дирихле, найдется как минимум один маркетолог, который провел анализ не менее пяти товаров.

Замечание. Задачу можно решить, применяя метод от противного.

Принцип Дирихле связан с понятием «более»  (зайцев больше, чем клеток). Верно и близкое утверждение, связанное с понятием «менее».

«Если в n клетках сидит менее   зайцев, то найдутся две клетки, в

17

которых сидит одинаковое количество зайцев (может быть, и ни одного)».

Рассмотрим задачу на применение этого утверждения.

Задача 4.

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

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

Доказательство:  Примем вузы за «клетки», а задания - за «зайцев». Так как  , что больше 90, то на основании утверждения, приведенного выше, найдутся два вуза, получившие одинаковое количество заданий (возможно, ни одного).

Замечание. Задача легко решается и методом от противного. Допустив, что каждый вуз получит разное количество заданий, мы получаем 0 + 1 + 2 + … + 14 = 105, что больше 90. Значит, обязательно найдутся два вуза, получившие одинаковое количество заданий (возможно, ни одного).

18

Заключение

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

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

Результаты эксперимента:

Вывод:

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

19

Литература

1. Виленкин Н.Я., В.В. Фирсов и др. Факультативный курс. Избранные вопросы математики. М.: Просвещение 1998 – 192 с.

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

3. Математическая логика // Википедия / http://ru.wikipedia.org

4. Успенский В.А., Верещагин Н.К., Плиско В.Е. Вводный курс математической логики. 2-е изд. – М.: Физматлит, 2002. – 128 с.

5.  Фарков А.В.  Методы решения олимпиадных задач. 10-11 классы. – М.: ИЛЕКСА, 2011. – 110 с. (Серия «Математика: элективный курс»).

20