Введение

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

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

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

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

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

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

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

Задачи:

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

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

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

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

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

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

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

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

Большой вклад в развитие логики внесли и русские ученые П.С. Порецкий (1846-1907), И.И. Жегалкин (1869-1947).

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

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

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

Основы теории множеств

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

Множеством называется совокупность определенных вполне различаемых объектов, рассматриваемых как единое целое. Создатель теории множеств Георг Кантор давал следующее определение множества - «множество есть многое, мыслимое нами как целое».

Отдельные объекты, из которых состоит множество, называются элементами множества.

Множества принято обозначать большими буквами латинского алфавита, а элементы этих множеств - маленькими буквами латинского алфавита. Множества записываются в фигурных скобках { }.

Принято использовать следующие обозначения:

a ∈ X - «элемент a принадлежит множеству X»;

a ∉ X - «элемент a не принадлежит множеству X»;

∀ - квантор произвольности, общности, обозначающий «любой», «какой бы не был», «для всех»;

∃ - квантор существования: ∃ y ∈ B - «существует (найдется) элемент y из множества B»;

∃! - квантор существования и единственности: ∃ !b ∈ C - «существует единственный элемент b из множества C»;

: - «такой, что; обладающий свойством»;

→ - символ следствия, означает «влечет за собой»;

⇔ - квантор эквивалентности, равносильности - «тогда и только тогда».

Множества бывают конечные и бесконечные . Множества называются конечным , если число его элементов конечно, т.е. если существует натуральное число n, являющееся числом элементов множества. А={a 1 , a 2 ,a 3 , ..., a n }. Множество называется бесконечным , если оно содержит бесконечное число элементов. B={b 1 ,b 2 ,b 3 , ...}. Например, множество букв русского алфавита - конечное множество. Множество натуральных чисел - бесконечное множество.

Число элементов в конечном множестве M называется мощностью множества M и обозначается |M|. Пустое множество - множество, не содержащее ни одного элемента - ∅ . Два множества называются равными , если они состоят из одних и тех же элементов, т.е. представляют собой одно и тоже множество. Множества не равны X ≠ Y, если в Х есть элементы, не принадлежащие Y, или в Y есть элементы, не принадлежащие Х. Символ равенства множеств обладает свойствами:

Х=Х; - рефлексивность

если Х=Y, Y=X - симметричность

если X=Y,Y=Z, то X=Z - транзитивность.

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

Подмножества. Отношение включения.

Множество Х является подмножеством множества Y, если любой элемент множества Х ∈ и множеству Y. Обозначается X ⊆ Y.

Если необходимо подчеркнуть, что Y содержит и другие элементы, кроме элементов из Х, то используют символ строгого включения ⊂ : X ⊂ Y. Связь между символами ⊂ и ⊆ дается выражением:

X ⊂ Y ⇔ X ⊆ Y и X≠Y

Отметим некоторые свойства подмножества, вытекающие из определения:

X ⊆ Х (рефлексивность);

→ X ⊆ Z (транзитивность);

Исходное множество А по отношению к его подмножествам называется полным множеством и обозначается I.

Любое подмножество А i множества А называется собственным множеством А.

Множество, состоящие из всех подмножеств данного множества Х и пустого множества ∅ , называется булеаном Х и обозначается β(Х). Мощность булеана |β(Х)|=2 n .

Счетное множество - это такое множество А, все элементы которого могут быть занумерованы в последовательность (м.б. бесконечную) а 1 , а 2 , а 3 , ..., а n , ... так, чтобы при этом каждый элемент получил ишь один номер n и каждое натуральное число n было бы в качестве номера дано одному и лишь одному элементу нашего множества.

Множество, эквивалентное множеству натуральных чисел, называется счетным множеством.

Пример. Множество квадратов целых чисел 1, 4, 9, ..., n 2 представляет собой лишь подмножество множества натуральных чисел N. Множество является счетным, так как приводится во взаимно однозначные соответствия с натуральным рядом путем приписывания каждому элементу номера того числа натурального ряда, квадратом которого он является.

Существует 2 основных способа задания множеств.

перечислением (X={a,b}, Y={1}, Z={1,2,...,8}, M={m 1 ,m 2 ,m 3 ,..,m n });

описанием - указывается характерное свойства, которым обладают все элементы множества.

Множество полностью определено своими элементами.

Перечислением можно задать только конечные множества (например, множество месяцев в году). Бесконечные множества можно задать только описанием свойств его элементов (например, множество рациональных чисел можно задать описанием Q={n/m, m, n ∈ Z, m≠0}.

Способы задания множества описанием:

а) заданием порождающей процедуры с указанием множества (множеств), которое пробегает параметр (параметры) этой процедуры - рекурсивный, индуктивный.

X={x: x 1 =1, x 2 =1, x k+2 =x k +x k+1 , k=1,2,3,...} - мн-во чисел Фибониччи.

{мн-во элементов х, таких, что х 1 =1,х 2 =1 и произвольное х k+1 (при к=1,2,3,...) вычисляется по формуле х k+2 =х k +х k+1 } или Х=.

С спрашивает себя, может ли его колпак быть зеленым. Если бы это было так, то А сразу же узнал бы, что на нем красный колпак, потому что только красный колпак на его голове мог бы заставить В поднять руку. Но тогда А вышел бы из комнаты. В стал бы рассуждать точно так же и тоже вышел бы из комнаты. Поскольку ни тот, ни другой не вышли, С заключил, что его собственный колпак должен быть красным.

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

Но прошло уже пять минут, а никто из них не выходит, следовательно, мой колпак красный».

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

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

Берем четыре красные и четыре зеленые марки, завязываем нашим «логикам» глаза и каждому из них наклеиваем на лоб по две марки. Затем снимаем с их глаз повязки и по очереди задаем А, В и С один и тот же вопрос: «Знаете ли вы, какого цвета марки у вас на лбу?» Каждый из них отвечает отрицательно. Затем мы спрашиваем еще раз у А и снова получаем отрицательный ответ. Но когда мы вторично задаем тот же вопрос В , тот отвечает утвердительно.

Какого цвета марки на лбу у В ?

Третью разновидность популярных логических головоломок составляют задачи о лжецах и тех, кто всегда говорит правду. В классическом варианте задачи речь идет о путешественнике, попавшем в страну, населенную двумя племенами. Члены одного племени всегда лгут, члены другого говорят только правду. Путешественник встречает двух туземцев. «Вы всегда говорите только правду?» - спрашивает он высокого туземца. Тот отвечает: «Тарабара». «Он сказал «да», - поясняет туземец поменьше ростом, знающий английский язык, - но он ужасный лжец». К какому племени принадлежит каждый из туземцев?

Систематический подход к решению заключался бы в выписывании всех четырех возможностей: ИИ, ИЛ, ЛИ, ЛЛ (И означает «истина», Л- «ложь») - и исключении тех из них, которые противоречат данным задачи. Ответ можно получить гораздо быстрее, если заметить, что высокий туземец должен ответить утвердительно независимо от того, лжет ли он или говорит правду. Поскольку туземец поменьше ростом сказал правду, он должен принадлежать к племени правдивых, а его высокий приятель - к племени лжецов.

Самую знаменитую задачу этого типа, усложненную введением вероятностных весов и не очень ясной формулировкой, можно найти довольно неожиданно в середине шестой главы книги английского астронома А. Эддингтона «New Pathways in Science ». «Если А, В, С и D говорят правду в одном случае из трех (независимо друг от друга) и А утверждает, что В отрицает, что С говорит, будто D лжец, то какова вероятность того, что D сказал правду?»

Ответ Эддингтона, 25/71 был встречен градом протестов со стороны читателей и породил смешной и путаный спор, который так и не был разрешен окончательно. Английский астроном Г. Дингл, автор рецензии на книгу Эддингтона, опубликованной в журнале Nature (March 1935), считал, что задача вообще не заслуживает внимания как бессмысленная и свидетельствует лишь о том, что Эддингтон недостаточно продумал основные идеи теории вероятностей. Американский физик Т. Стерн (Nature, June 1935) возразил на это, заявив, что, по его мнению, задача отнюдь не бессмысленна, но данных для ее решения недостаточно.

В ответ Дингл заметил (Nature, September 1935), что если встать на точку зрения Стерна, то данных для решения вполне достаточно и ответ будет 1/3. Тут в драку вступил Эддингтон, опубликовав (Mathemetical gazette, October 1935) статью с подробным объяснением того, как он получил свой ответ. Спор завершился еще двумя статьями, появившимися в том же журнале, автор одной из них выступил в защиту Эддингтона, а в другой выдвигалась точка зрения, отличная от всех прежних.

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

1. Никто из четверых не промолчал.

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

3. Ложное утверждение совпадает со своим отрицанием, а ложное отрицание совпадает с утверждением.

Все четверо лгут независимо друг от друга с вероятностью 1/3, то есть в среднем любые два из трех их высказываний ложны. Если правдивое высказывание обозначить буквой И , а ложное - буквой Л , то для А, В, С и D мы получим таблицу, состоящую из восьмидесяти одной различной комбинации. Из этого числа следует исключить те комбинации, которые невозможны в силу условий задачи.

Число допустимых комбинаций, оканчивающихся буквой И (то есть правдивым - истинным - высказыванием D ), следует разделить на общее число всех допустимых комбинаций, что и даст ответ.

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

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

Так женская логика нанесла удар моему мужскому тщеславию. Не задевает ли она немножко и ваше авторское самолюбие?

Ответы

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

Поскольку миссис Уайт зовут Маргарет (условие 5), для имен двух других жен у нас остаются только две возможности: а) Элен Блейк и Беатрис Браун или б) Элен Браун и Беатрис Блейк.

Допустим, что имеет место вторая из возможностей. Сестрой Уайта должна быть либо Элен, либо Беатрис. Но Беатрис не может быть сестрой Уайна, потому что тогда братом Элен был бы Блейк, а двумя деверями Блейк оказались бы Уайт (брат его жены) и Браун (муж его сестры); Беатрис же Блейк не состоит в браке ни с одним из них, что противоречит условию 4. Следовательно, сестрой Уайта должна быть Элен. Отсюда в свою очередь мы заключаем, что сестру Брауна зовут Беатрис, а сестру Блейка - Маргарет.

Из условия 6 следует, что мистера Уайта зовут Артур (Браун не может быть Артуром, так как подобная комбинация означала бы, что Беатрис красивее самой себя, а Блейк не может быть Артуром, поскольку из условия 5 нам известно его имя: Уильям). Итак, мистер Браун может быть только Джоном. К сожалению, из условия 7 мы видим, что Джон родился в 1868 году (за 50 лет до подписания мирного договора). Но 1868 год - високосный, поэтому Элен должна быть старше своего мужа на один день больше тех 26 недель, о которых говорится в условии 3. (Из условия 4 мы знаем, что она родилась в январе, а из условия 3 - что ее муж родился в августе. Она могла бы быть ровно на 26 недель старше своего мужа, если бы ее день рождения приходился на 31 января, а его - на 1 августа и если бы между этими датами не было 29 февраля!) Итак, вторую из возможностей, с которой мы начали, следует отбросить, что позволяет нам назвать имена жен: Маргарет Уайт, Элен Блейк и Беатрис Браун. Никакого противоречия здесь нет, поскольку мы не знаем года рождения Блейка. Из условий задачи можно заключить, что Маргарет - сестра Брауна, Беатрис - сестра Блейка, а Элен - сестра Уайта, но вопрос о том, как зовут Уайта и Брауна, остается нерешенным.

В задаче с марками у В имеются три возможности. Его марки могут быть: 1) обе красными; 2) обе зелеными; 3) одна зеленой, а другая красной. Предположим, что обе марки красные.

После того как все трое ответили по одному разу, А может рассуждать так: «Марки у меня на лбу не могут быть обе красными (потому что тогда С увидел бы четыре красные марки и сразу узнал бы, что у него на лбу две зеленые марки, а если бы у С обе марки были зелеными, то В , увидев четыре зеленые марки, понял бы, что у него на лбу две красные марки). Поэтому у меня на лбу одна зеленая и одна красная марки».

Но когда А спросили второй раз, он не знал, какого цвета его марки. Это позволило В отбросить возможность того, что обе его собственные марки красные. Рассуждая точно так же, как и А, В исключил случай, когда обе его марки зеленые. Следовательно, у него осталась единственная возможность: одна марка зеленая, другая красная.

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

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

Как выразился декан математического факультета Бруклинского колледжа У. Манхеймер, это изящное решение исходит из того обстоятельства, что в совершенстве владеют логикой не А, В и С (как о том сказано в условии задачи), а Рэймонд Смаллиан!

В задаче Эддингтона вероятность того, что D говорит правду, составляет 13/41. Все комбинации истины и лжи, которые содержат нечетное число раз ложь (или истину), следует отбросить как противоречащие условиям задачи. В результате число возможных комбинаций понижается с 81 до 41, из них только 13 заканчиваются правдивым высказыванием D . Поскольку А, В и С говорят правду в случаях, которые отвечают точно такому же числу допустимых комбинаций, вероятность сказать правду у всех четырех одинакова.

Используя символ эквивалентности

означающий, что соединенные им высказывания либо оба истинны, либо оба ложны (тогда ложное высказывание истинно, в противном случае оно ложно), и символ отрицания ~, задачу Эддингтона на языке исчисления высказываний можно записать так:

или после некоторых упрощений так:

Таблица истинности этого выражения подтверждает уже полученный ответ.