Раздел 1. Множества и отображения

Элементы математической логики

Методические указания и контрольные задания для студентов Авиационного колледжа

Ростов-на-Дону

Содержание:

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

Раздел 1. Множества и отображения. Операции над множествами……….5

Мощность множества………………………………………………………..11

Отношения…………………………………………………………………...13

Раздел 2. Исчисление высказываний. Высказывания, операции над высказываниями………………………………………………………………………….16

Нормальные формы………………………………………………………..21

Полином Жегалкина………………………………………………………..25

Исчисление высказываний (ИВ)…………………………………………..26

Раздел 3. Исчисление предикатов. Определение предиката. Кванторы……………………………………………………………………………………28

Формулы логики предикатов. Равносильность формул …………………31

Раздел 4.Элементы теории алгоритмов……………………………………36

Вычислимые, частично рекурсивные и общерекурсивные функции…….40

Машины Тьюринга…………………………………………………………..41

Контрольная работа. Вариант №1…………………………………………..44

Контрольная работа. Вариант № 2………………………………………….46

Контрольная работа. Вариант №3…………………………………………..48

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

«…... Употребляйте с пользой время:

Учиться надо по системе.

Сперва хочу Вам в долг вменить

На курсы логики ходить.

Ваш ум, не тронутый доныне,

На них приучат к дисциплине,

Чтоб взял он направленья ось,

Не разбредаясь вкривь и вкось».

В. Гете «Фауст» ч. I «Ночь»

Введение

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

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

Логика как наука сформировалась очень давно — в IV в. до н.э. Ее создал древнегреческий ученый Аристо­тель. В течение многих веков логика почти совсем не развивалась. Это, конечно, свидетельствует о гениально­сти Аристотеля, которому удалось создать столь полную научную систему, что, казалось, «не убавить, не приба­вить».

В XVII в. великий немецкий ученый Лейбниц заду­мал создать новую логику, которая была бы «искусст­вом исчисления». В этой логике, по мысли Лейбница, каждому понятию соответствовал бы символ, а рассуж­дения имели бы вид вычислений. Эта идея Лейбница, не встретив понимания современников, не получила распро­странения и развития.

Впервые идеи Лейбница реализовал Д. Буль в 40-х гг. девятнадцатого столетия. Он создал алгебру, в которой буквами обозначены высказывания, и это привело к появлению алгебры высказываний. Применение математики к логике позволило представить логические теории в новой удобной форме и применить вычислительный аппарат к решению задач, малодоступных че­ловеческому мышлению из-за особенностей человеческой психики. Современная математическая логика определяется как раздел математики, посвященный изучению математических доказательств и вопросов основания математики. Одна из главных причин широкого распространения математи­ческой логики— применение аксиоматического метода в построении раз­личных математических теорий. В нем сначала выбираются некоторые поня­тия, которые не определяются, а лишь поясняются. Затем без доказательства принимается некоторый набор аксиом, а уже потом из этих аксиом логически строго выводятся и доказываются все оставшиеся положения теории.

Самым ранним примером аксиоматической теории являются "Начала" Евклида. Однако система аксиом, положенная Евклидом в основу теории, не является единственной и содержит небесспорный пятый постулат (аксиому о параллельных прямых).

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

К системе аксиом предъявляется одно непременное требование — она долж­на быть непротиворечивой. Это значит, что из данной системы аксиом (не­противоречивой) нельзя логическим путем вывести два противоречащих друг другу утверждения. Основным методом доказательства непротиворечивости является метод моделирования, или метод интерпретаций, который строится для математических теорий на базе теории множеств.

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

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

Раздел 1. Множества и отображения

Не нашли, что искали? Воспользуйтесь поиском: