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

УДК 517

Принято на заседании кафедры общей математики

Рецензенты:

кандидат физ.-мат.наук, доцент кафедры

общей математики КФУ В.А. Сочнева,

кандидат физ.-мат.наук, доцент кафедры

общей математики КФУ Е.П. Аксентьева

Математика.Учебно-методическое пособие / М.С. Малакаев, Е.А.Широкова.– Казань: Казан. ун-т, 2016 – 64 с.

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

В пособии рассмотрены темы «Элементы математической логики», «Элементы теории множеств», «Комбинаторика»,«Элементы теории графов», «Производные и интегралы», «Элементы теории вероятностей», «Элементы математической статистики» с набором примеров по каждой теме.

© Малакаев М.С., Широкова Е.А., 2016

© Казанский университет,2016

Содержание

1.Элементы математической логики………………………………………..4

2. Элементы теории множеств……………………………………………………17

3.Элементы теории графов………………………………………………….23

4. Функции…………………………………………………………………………33

5.Основные понятия и теоремы теории вероятностей…………………… 46

6.Элементы математической статистики ………………………………….66

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

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

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

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

Логика– это наука, изучающая формы и законы мышления. Само слово произошло от греческого logos, что означает «слово, понятие, разум». Законы и правила формальной логики необходимо знать для построения правильных рассуждений. Согласно основному принципу логики правильность рассуждения (вывода) определяется только его логической формой и не зависит от конкретногосодержания входящихв него рассуждений.Отличительной особенностью правильного вывода является то, что из истинных утверждений всегда получаются истинные заключения. Это позволяет из одних истин получать другие с помощью только рассуждений, разума и без обращения к опыту.

Как самостоятельная наука, логика оформилась в трудах греческого философа Аристотеля (384-322 гг. до н.э.). Он систематизировал известные до него сведения, и эта система стала впоследствии называться традиционной или аристотелевой логикой. Аппарат этой логики оказался настолько мощным, что, например, на его основе известный средневековый философ и богослов Фома Аквинский осуществил обоснование всей христианской теологии. Немецкий математик Лейбниц впервые высказал мысль о том, что основные понятия логики должны быть обозначены символами, которые соединяются по определенным правилам, и это позволяет всякие рассуждения заменить вычислением. Он писал, что единственное средство улучшения умозаключений состоит в уподоблению их математическим, «чтобы ошибочность их можно было увидеть глазами, и если между людьми возникают разногласия, достаточно было бы сказать «Вычислим!» и станет ясно, кто прав». Это проделал в своей работе «Исследование законов мысли» Джордж Буль, в результате чего логическая теория приняла вид обычной алгебры и получила название алгебры высказываний или булевой алгебры, которую мы и будем изучать.

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

Высказыванием называется повествовательное предложение, про которое всегда определенно можно сказать, является оно истинным (И) или ложным (Л). Примеры высказываний: «Дважды два четыре», «Земля вращается вокруг Солнца», «3>5», «10 – нечетное число», «На улице идет дождь». Побудительные предложения («Кругом», «Идите к доске»), вопросительные («Сколько времени?») и восклицательные («Ак Барс – чемпион!») высказываниями не являются. Логические операции на множестве высказываний задаются аксиоматически с применением таблиц истинности, указывающих значение (И или Л) результата операции при задании значений исходных высказываний.

Аксиоматика операций над высказываниями.

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

И	Л
Л	И

Пример. : «∆АВС остроугольный.», тогда : «неверно, что ∆АВС остроугольный» или : «∆АВС прямоугольный или тупоугольный.» Пример показывает, что отрицание не обязательно содержит частицу «не» в явном виде, – отрицание может содержаться и в смысловом оттенке фразы.

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

И	И	И
И	Л	Л
Л	И	Л
Л	Л	Л

Предложение «Солнце светит и на улице тепло» представляет собой конъюнкцию двух высказываний Х: «Солнце светит.» и У: «На улице тепло».

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

A
И	И	И
И	Л	И
Л	И	И
Л	Л	Л

Заметим, что в обыденной речи союз «или» употребляется в двух смыслах:

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

На самом деле это два разных союза. У древних римлян в качестве неразделительного «или» использовалось слово «vel», а разделительного слово «aut». Дизъюнкция это неразделительное «или».

Рассмотренные три операции называют булевыми.

4) Импликация. Операция импликации соответствует объединению двух высказываний с помощью союза «если А , то В». Она обозначается А→В. Например, «Если студент-контрактник в течение 2-х сессий получал только отличные отметки, то по его ходатайству деканат может перевести его на бюджетную форму обучения». Импликация двух высказываний А и В ложна тогда и только тогда, когда высказывание А истинно, а В – ложно. Высказывание А называется посылкой импликации, а высказывание В – следствием. Таблица истинности имеет вид

А	В	А→В
И	И	И
И	Л	Л
Л	И	И
Л	Л	И

Приведем несколько выражений, которые считаются имеющими тот же смысл, что и «если А , то В» (где А и В высказывания): «А влечет В», «А только тогда, когда В», «В при условии А», «А, только если В», «В, если А». Следует уточнить, что логическими операциями никак не учитывается смысл высказываний в них участвующих. Высказывания рассматриваются как объекты, обладающие единственным свойством быть истинными или ложными. Например: Пусть Х: «Луна сделана из зеленого сыра», а У: «2+2=5», тогда согласно таблице раз Х ложно, то импликация Х→ У будет истинна , хотя никакой связи по смыслу между Х и У нет. Точно так же, если У– это «2+2=4», то Х→ У – истинно , причем совершенно независимо от того есть ли связь между «Луна состоит из зеленого сыра» и «2+2=4». Такое уточнение смысла импликации «если Х, то У» не противоречит обыденному смыслу. Например обещание «Если мне подарят велосипед, то я дам тебе покататься» воспринимается как ложь только в том случае, если мне подарили велосипед, а покататься на нем я не дал.

5) Эквиваленция. Эквиваленция обозначается А↔В (читается: А эквивалентно В или А равносильно В или А тогда и только тогда, когда В). Например, «Четное число делится на 6 тогда и толькотогда, когдаоно делится на 3» или «Студент допускается к сессии в том и только в том случае, если он сдаст все зачеты». Эквиваленция двух высказываний А и В истинна тогда и только тогда, когда истинности высказываний совпадают. Поэтому таблица истинности для эквиваленции имеет вид

А	В	А↔В
И	И	И
И	Л	Л
Л	И	Л
Л	Л	И