Учебное пособие по математической логике для студентов заочного отделения




НазваниеУчебное пособие по математической логике для студентов заочного отделения
страница1/5
Дата публикации28.08.2013
Размер0.96 Mb.
ТипУчебное пособие
skachate.ru > Математика > Учебное пособие
  1   2   3   4   5



МАТЕМАТИЧЕСКАЯ ЛОГИКА

Д.В. Бутенина и В.М. Лагодинский

Бутенина Д.В., Лагодинский В.М.

Математическая логика. Учебное пособие по математической логике для студентов заочного отделения

СПбГУАП
В учебном пособии дано краткое изложение основ теории множеств, алгебры высказываний, исчисления высказываний, логики предикатов и исчисления предикатов. Приведены варианты контрольных работ.

Пособие предназначено для самостоятельного изучения математической логики студентами заочной формы обучения направления “Информатика и вычислительная техника”. Оно может быть полезна также студентам других специальностей при изучении дисциплин со схожей тематикой.
УДК 004421(075.8)

ББК 2212я73
Учебное издание
Бутенина Дина Викторовна

Лагодинский Владимир Меерович
^ МАТЕМАТИЧЕСКАЯ ЛОГИКА
Учебное пособие

Введение. Предмет математической логики

и ее использование в инженерной практике выпускников СПбГУАП

Логику принято определять как науку о законах мышления. Но механика – наука о законах движения – утверждает, например, что любое тело с массой m под действием силы движется с ускорением . Вряд ли кто-нибудь станет утверждать, что любой человек всегда мыслит логично. Более того, если бы это было так, человек не мог бы открыть ничего принципиально нового, не следующего автоматически из старого. Кроме того, такое определение относит логику к наукам о человеке, делает ее разделом психологии человека. Но почему и для чего человек размышляет? Размышляя, человек или ищет причину, если известно следствие (этим занимаются, например, следователи и исследователи), или ищет следствие по известной причине для того, чтобы затем действовать целесообразно, то есть либо теоретически выводит причину из следствия, либо наоборот.

Но и животные обычно действуют целесообразно. Используют ли они логику? Известно, что шимпанзе, увидев подвешенный банан и груду ящиков, сначала отходит в сторону, принимает позу роденовского мыслителя, а через некоторое время ставит ящики один на другой под бананом и добирается до него. Это нельзя объяснить случайностью или рефлексами и даже опытом. Но другие животные руководствуются безусловными и условными рефлексами и опытом, и их поведение тоже целесообразно. И даже растения живут ‘‘разумно’’: осенью сбрасывают листья, яркими цветами привлекают насекомых, а некоторые насекомых едят.

Несколько другое определение представляет логику ‘‘как науку о правильных способах рассуждения, т. е. таких способах рассуждения, при которых из верных исходных положений получаются верные результаты’’ [2]. С этим можно согласиться, но возникает вопрос: почему эти способы приводят к верным результатам? И что такое эти верные результаты?

Очевидно, верные результаты – это такие результаты, которые соответствуют реальному миру, который нас окружает. Иначе говоря, эти способы рассуждения правильны потому, что точно соответствуют реальному миру, его самым основным законам. Можно сказать, следовательно, что законы логики отображают самые основные законы реального мира – законы причинно-следственных связей, а не устройство мозга человека. Рассуждают люди и (может быть) иногда человекообразные обезьяны, вряд ли рассуждают другие животные, и уж точно не рассуждают растения. Но в ‘‘устройстве’’ их всех отражены законы причинно-следственных связей явлений реального мира, важных для их жизнедеятельности. Для растений и низко организованных животных цепочек причинно связанных жизненно важных явлений немного, и они могут быть отражены в их генах. Для более высокоорганизованных животных (таких, как хищные млекопитающие или приматы) их гораздо больше, и они отражены в тех связях, которые существуют в их мозгу и могут меняться в течение жизни под воздействием личного опыта.

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

Мысли выражаются предложениями и целыми последовательностями предложений на каком-либо языке. Предложения состоят из слов, которые соединяются в предложения по законам данного языка. Эти законы изучает лингвистика. Известный лингвист Л.В. Щерба предлагал студентам проанализировать ‘‘фразу’’: ``Глокая куздра штеко будланула бокра и курдячит бокренка''. Есть ли смысл в этой фразе? Оказывается, есть! Он заключается в тех частях слов, которые играют, казалось бы, служебную роль: окончаниях и суффиксах, а также в союзе ‘‘и’’. Корни слов могут быть разными, но этот смысл, связь этих слов в едином утверждении одна и та же. И эта связь (выражаемая в каждом языке своими средствами) отображает отношения между объектами, реальными или воображаемыми. Эти отношения могут быть самыми разнообразными, и человек познает эти отношения, вырабатывая понятия, создавая слова для обозначения этих понятий. Рассуждения человека, если они правильны, связывают эти слова, то есть понятия, по определенным законам, которые отображают законы реального мира. Следовательно, изучая законы правильного мышления, мы изучаем законы реального мира, именно законы причинно-следственных связей в реальном мире.

Итак, логика – это наука о причинно-следственных связях. Обязательно ли это связи реального мира? В принципе, необязательно. Логика – наука теоретическая. Мы можем конструировать (выдумывать) любые причинно-следственные связи, и некоторые логики этим занимаются. Чаще, однако, ‘‘искаженные’’ миры придумывают писатели-фантасты (например, ‘‘Обмен разумов’’ и ‘‘Оптимальный вариант’’ Роберта Шекли или ‘‘Конец Вечности’’ Айзека Азимова). При чтении этих произведений очень ощущаются трудности, испытываемые авторами при стараниях свести концы с концами, и, в то же время, читая эти произведения мы обращаем больше внимания, чем обычно, на логику нашего мира.

Конечно, основные законы реального мира знать необходимо любому человеку. Но они кажутся такими естественными: из двух противоположных утверждений одно обязательно истинно, два противоположных утверждения не могут быть истинными одновременно – казалось бы, каждый человек в своих рассуждениях руководствуется этими законами. Но иногда рассуждения, кажущиеся вполне логичными, приводят к парадоксам. С древности известны апории Зенона об Ахиллесе, который якобы никогда не догонит черепаху, о стреле и другие. Парадокс ‘‘Лжец’’ состоит в следующем: некто говорит, что он всегда лжет. Солгал он или сказал правду? Существование парадоксов показывает, что рассуждать правильно не так просто. Особенно трудно рассуждать, если требуется учесть очень много различных сведений и/или связи между ними сложны и многочисленны.

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

Теоретическая наука также зародилась в древности. Шарообразность Земли была доказана наблюдениями лунных затмений: тень Земли на Луне имеет круглую форму; но только шарообразные предметы всегда отбрасывают круглую тень, следовательно, Земля – шар. Эвклид построил геометрию, сформулировав небольшое количество аксиом и логически выведя из них много теорем. Такой способ построения теории давно признан идеальным. Философ Спиноза в аксиоматическом виде построил свою ‘‘Этику’’, а физик и математик Ньютон – механику, которую теперь называют классической, или ньютоновской.

Еще до новой эры было осознано, что правила рассуждений, которые приводят к верным результатам, не зависят от предмета этих рассуждений. Это позволило Аристотелю построить логику как формальную теорию. Последующее развитие математики, во-первых, потребовало выяснения основ этой науки, во-вторых, показало возможность построения логики как математической науки. Впервые мысль о возможности математизации логики высказал немецкий математик Лейбниц в восемнадцатом веке. Но реализовать эту идею удалось только в девятнадцатом веке английскому математику Д. Булю. С тех пор математическая логика развилась в самостоятельную математическую науку. Более того, математическая логика стала играть роль метаматематики, то есть науки, занимающейся законами построения всей математики. Символика математической логики стала широко использоваться во всех математических науках. Крупный вклад в развитие математической логики внесли выдающийся немецкий математик Д. Гильберт и такие математики, как Пост, Черч, Тьюринг, Гедель. После появления современных вычислительных машин математическая логика стала необходимой для разработки их программного обеспечения, языков программирования. Большое значение приобрел один из разделов математической логики – теория алгоритмов. Это определяет необходимость знания основ математической логики для современного инженера, специальность которого связана с программированием и разработкой устройств автоматики.
^ 1. Элементы теории множеств
Теория множеств является основой всех разделов современной математики, а ее основы заложил немецкий математик Георг Кантор. Главная заслуга Г. Кантора состоит в открытии принципов обращения с бесконечными множествами. В математической логике такие множества встречаются редко, но язык теории множеств в ней широко используется.

Понятие множества является одним из основных понятий в математике и поэтому обычно не определяется. Его можно лишь пояснить как совокупность объектов произвольной природы, которые называются элементами этого множества. Элементами множества A могут быть и другие множества, с одним ограничением: множество A не может включать себя в качестве элемента. Тот факт, что объект a является элементом множества A, обозначается следующим образом:

.

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



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



Здесь R – множество вещественных чисел. Другие числовые множества: N – множество натуральных чисел (в настоящее время к этому множеству обычно относят все целые неотрицательные числа: 0; 1; 2 ), Z – множество всех целых чисел, Q – множество всех рациональных чисел. Множества и называются равными, если они состоят из одних и тех же элементов. Множество называется подмножеством множества (это обозначается формулой ), если любой элемент множества является также элементом множества . Отсюда следует, что для доказательства равенства двух множеств достаточно доказать, что одновременно и . Очевидно, любое множество является подмножеством самого себя: . Бывает заранее неизвестно, содержит ли некоторое множество хотя бы один элемент. В связи с этим вводится понятие пустого множества, не содержащего элементов. Это множество обозначается символом Ш. Пустое множество по определению считается подмножеством любого множества. Любое подмножество множества , кроме его самого и пустого множества, называется собственным подмножеством множества .

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

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



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

1) Рефлексивность: при всех (если отношение рефлексивно, то любой элемент находится в этом отношении к самому себе).

2) Симметричность: если , то .

3) Антисимметричность: если и , то ( и – один и тот же элемент).

4) Транзитивность: если и , то .

Если отношение рефлексивно, симметрично и транзитивно, то оно называется отношением эквивалентности. Такое отношение разделяет множество, на котором оно определено, на непересекающиеся классы эквивалентности. Например, если для точек плоскости ввести отношение равноудаленности от некоторой одной точки этой плоскости, то плоскость представляется объединением окружностей с центром в этой точке.

Если отношение рефлексивно, антисимметрично и транзитивно, оно называется отношением (частичного) порядка. Такие отношения часто обозначается так: (читается предшествует ). Это можно обозначить и так: . Примеры отношений порядка: . Но если для любых двух вещественных чисел справедливо либо , либо , то существуют такие множества и , что несправедливо ни , ни . Множество множеств является частично упорядоченным, в нем есть несравнимые элементы. Множество вещественных чисел R является упорядоченным – в нем нет несравнимых элементов. Множество натуральных чисел является вполне упорядоченным – в нем есть наименьший элемент.

Если существует правило, которое каждому элементу множества сопоставляется один из элементов множества , то говорят, что существует отображение множества во множество и это обозначается выражением . Элемент , сопоставляемый этим отображением элементу называется образом элемента , а элемент называется прообразом элемента . Отображения бывают трех видов: 1) сюръективные отображения (сюръекции); 2) инъективные отображения (инъекции); 3) биективные отображения .

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

Множества и называются эквивалентными, если существует хотя бы одна биекция . Еще про такие множества говорят, что они имеют одинаковую мощность. Понятие мощности – это обобщение числа элементов на бесконечные множества. Если множество – конечное , то есть содержит лишь конечное число элементов, то эквивалентным ему может быть лишь конечное множество. Если множество содержит подмножество, эквивалентное множеству , то его мощность не меньше мощности множества . Если множество содержит подмножество, эквивалентное множеству , и одновременно множество содержит подмножество, эквивалентное множеству , то множества и имеют одинаковую мощность (теорема Бернстайна [3]).

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

Теорема 1. Объединение счетного числа конечных множеств – не более чем счетно.

Теорема 2. Объединение счетного числа счетных множеств не более чем счетно. Доказательства этих теорем в [4].

Из теоремы 2 легко следует счетность множества рациональных чисел Q.

Но существуют множества, имеющие мощность большую, чем мощность счетного множества.

Теорема 3. Мощность множества вещественных чисел на отрезке имеет мощность, большую .

Доказательство. Множество содержит подмножество , имеющее мощность , поэтому мощность множества не меньше чем . Предположим, что она равна . Тогда все элементы множества можно перенумеровать, и расположить их в виде бесконечной последовательности:
; ; ; ; ,

где – цифры 0, 1, 2, , 9. Теперь покажем, что, в противоречие с предположением, эта последовательность содержит не все элементы множества . В частности, она не содержит число, которое имеет вид , где – цифры 0, 1, 2, , 9, если – любая цифра, кроме , – любая цифра, кроме , и так далее. Тогда от первого числа последовательности оно отличается первой цифрой после запятой, от второго – второй цифрой после запятой и так далее. Итак, мощность множества больше . Теорема доказана.

Мощность этого множества носит название мощности континуума и обозначается обычно символом . Можно показать (см. [4]), что мощность точек любого промежутка числовой прямой и всей прямой R равна . Более того, можно показать [4], что мощность множества тоже равна .

Существуют и множества с мощностями, большими . Можно показать [4], что мощность множества подмножеств множества строго больше мощности множества . Мощность множества отображений множества во множество также строго больше мощностей обоих этих множеств. Таким образом, существуют множества как угодно большой мощности.

Остается нерешенной проблема: существуют ли множества мощности, промежуточной между и ? Известно лишь, что ни положительный, ни отрицательный ответ на этот вопрос не противоречит всей современной теории множеств.
  1   2   3   4   5

Похожие:

Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие по ботанике для студентов 3 курса заочного отделения...
Учебное пособие предназначено для самостоятельной работы студентов 3 курса заочного отделения фармацевтического факультета. Пособие...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие для самостоятельной работы студентов заочного отделения...
Учебное пособие предназначено для для самостоятельной работы студентов заочного отделения неязыков специальностей вузов, ранее изучавших...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие для самостоятельной работы студентов заочного отделения...
Учебное пособие предназначено для для самостоятельной работы студентов заочного отделения неязыков специальностей вузов, ранее изучавших...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие по органической химии для самостоятельной работы...
Учебное пособие предназначено для самостоятельной работы студентов II курса заочного отделения фармацевтического факультета при выполнении...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие по фармацевтической химии для студентов 4 курса заочного...
Авторы учебного пособия для студентов 4 курса заочного отделения фармацевтического факультета «Общие и частные методы анализа лекарственных...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие содержит характеристику основных разделов фармацевтической...
В пособии приведена рабочая программа по фармацевтической химии для студентов заочного отделения, даны рекомендации по её освоению...
Учебное пособие по математической логике для студентов заочного отделения iconУчебное пособие по органической химии для самостоятельной работы студентов
Учебное пособие предназначено для самостоятельной работы студентов II курса заочного отделения фармацевтического факультета при выполнении...
Учебное пособие по математической логике для студентов заочного отделения iconРекомендации о разработке методических указаний и контрольных заданий...
Разработчик: методист заочного учебного отделения высшего профессионального образования С. С. Кудрявцева
Учебное пособие по математической логике для студентов заочного отделения iconСамостоятельная работа, часов
Смолова Л. М. Химия. Рабочая программа, методические указания, элементы теории, вопросы для самопроверки и контрольные задания для...
Учебное пособие по математической логике для студентов заочного отделения iconКонтрольная работа №2 по английскому языку для студентов заочного...
Данное пособие можно взять в библиотеке Политехнического колледжа или получить в электронном виде. Также необходимо изучить материалы...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2014
контакты
skachate.ru
Главная страница