Лекции по "Математике"

Z - множество всех целых чисел; 

Q - множество всех рациональных чисел; 

R - множество всех действительных чисел;  

C - множество всех комплексных чисел;

Z₀ - множество всех неотрицательных целых чисел.

   Запись  (или ) означает, что элемент a принадлежит множеству A.

   Запись  (или ) означает, что элемент a не принадлежит множеству A.

Элементы  теории множеств

Множества

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

1. Должно существовать правило, позволяющее определить, принадлежит ли указанный элемент данной совокупности.
2. Должно существовать правило, позволяющее отличать элементы друг от друга. (Это, в частности, означает, что множество не может содержать двух одинаковых элементов).

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

Если  каждый элемент множества  является также и элементом множества , то говорят, что множество является подмножеством множества :

Подмножество  множества называется собственным подмножеством, если

Используя понятие множества можно построить  более сложные и содержательные объекты.

Операции  над множествами

Основными операциями над множествами являются объединение, пересечение и разность.

Определение 1. Объединением двух множеств называется новое множество

Определение 2. Пересечением двух множеств называется новое множество

Определение 3. Разностью двух множеств называется новое множество

Если  класс объектов, на которых определяются различные множества обозначить (Универсум), то дополнением множества называют разность

 

Парадоксы теории множеств

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

Аксиома Фреге. Для любого свойства Р существует множество {x | Р(x)} всех объектов х, обладающих свойством Р.

Парадокс  Рассела. Пусть X - множество всех множеств, которые не являются собственными элементами. Тогда X в том и только том случае является собственным элементом, когда  оно не является собственным элементом.

Доказательство. Предположим, что XÎX. Тогда X является собственным  элементом и, значит, не входит в X по определению X. Таким образом, XÎXÞXÏX. С другой стороны, если XÏX то X не является собственным элементом и, значит, входит в X по определению X. Таким образом. XÏXÞ XÎX.

Классические  формулировки парадокса Рассела.

Парадокс  Рассела можно сформулировать и не используя теорию множеств. Вот три классические формулировки этого парадокса.

Парадокс  парикмахера. Вождь афинской демократии Клисфен повелел, чтобы единственный парикмахер города брил тех и только тех граждан Афин, которые не бреются сами. Должен ли парикмахер брить себя?

Парадокс  каталога. Библиотека Борхеса решила составить библиографический каталог, в который входят те и только те каталоги, которые не включают себя. Включает ли такой каталог себя?

Парадокс  самоуважения. Имеет ли профессор  Конте самоуважение, если он уважает только тех, кто не уважает себя?

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

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

Но ведь такого числа не существует. Именно так: все “логические парадоксы” (не путать с “лингвистическими” или “семантическими” парадоксами, типа парадокса лжеца) построены по следующей схеме: предположим, что существует некоторый объект X. Тогда этот объект X одновременно обладает и не обладает некоторым свойством. Но это в точности и значит, что требуемого объекта X не существует, именно так устроены доказательства от противного, например, доказательство иррациональности числа  или бесконечности множества простых чисел. Единственная разница состоит в том, что в парадоксе Пиглета противоречивость условия очевидна сразу, а в парадоксе Рассела условие не кажется противоречивым - хотя и является таковым. Таким образом, парадокс Рассела всего лишь доказывает (от противного), что не существует множества Y = {X | XÏX} всех множеств, не являющихся собственными элементами, и, тем самым, не для любого свойства Р обязано существовать множество {х | Р(х)}. Но никто из серьезных математиков никогда и не утверждал, что любое свойство должно определять множество.

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

{1, 2}; {2}; {2, 3, 4}; {3, 4}; {3, 4, 5, 6}; {4, 5, 6}…

Возникает вопрос: сколько элементов будет  в этом бесконечном множестве? Количество элементов возрастает. Но на первом шаге мы убрали из множества первый элемент, на втором шаге – второй и  так далее. Если рассматривать каждый конкретно взятый элемент, то окажется, что его нет во множестве (ведь nÞ¥).

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

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

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

Другой  способ – аксиоматический (система  аксиом Цермело–Френкеля, система  аксиом Геделя–Бернайса). 
 

5. Элементы  математической логики: высказывания; логические связки; выполнимость и  противоречивость

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

D: 5 – простое число

E: 12 = 2² · 3

F: земля – спутник Луны

G: Функция y = cos x является четной

H: если и - различные векторы, то - ≠ -

Логические  операции (связки):

Определение1.1.1 отрицанием А называется высказывание  
 
 

6. Графы, их типы. Задача коммивояжера

Граф-совокупность точек (вершин) и совокупность пар  этих точек (не обязательно всех), соединенных  линиями (рис. 1,л). Если на графе линии  ориентированы (т.е. стрелками показано направление связи вершин), они  наз. дугами, или ветвями; если неориентированы,-ребрами. Соотв. граф, содержащий только дуги, наз. ориентированным, или орграфом; только ребра-неориентированным; дуги и ребра-смешанным. Граф, имеющий кратные ребра, наз. мультиграфом; граф, содержащий только ребра, принадлежащие двум его непересекающимся подмножествам (частям),-двудольным; дуги (ребра) и (или) вершины, к-рым отвечают определенные веса или числовые значения к.-л. параметров,-взвешенным. Путь в графе-чередующаяся последовательность вершин и дуг, в к-рой ни одна из вершин не повторяется (напр., a, b на рис. 1,a); контур-замкнутый путь, в к-ром первая и последняя вершины совпадают (напр.,f, h); петля-дуга (ребро), к-рая начинается и кончается в одной и той же вершине. Цепь графа-последовательность ребер, в к-рой ни одна из вершин не повторяется (напр., с, d, e); цикл-замкнутая цепь, в к-рой ее начальная и конечная вершины совпадают. Граф наз. связным, если любая пара его вершин соединена цепью или путем; в противоположном случае граф наз. несвязным.

Типы  графов

Содержание

• Теорема о двудольности

Граф G = (X, A) называют полным, если для любой пары вершин х_i и х_j в X существует ребро (х_i, х_j) в неориентированном графе

G=(X,A)

т. е. для  каждой пары вершин графа G должна существовать по крайней мере одна дуга, соединяющая их (рис. 5.1,а).

Граф  G =(X, A)называется симметрическим, если в множестве дуг A для любой дуги (х_i, х_j) существует также противоположно ориентированная дуга (х_j, х_i) (рис. 5.1,б).

 
Рис. 5.1.  а – полный граф; б – симметрический граф; в – антисимметрический граф; г – полный симметрический;

Антисимметрическим называется такой граф, для которого справедливо следующее условие: если дуга (х_i, х_j) A, то во множестве A нет противоположно ориентированной дуги, т. е. ( х_j, х_i) A (рис. 5.1,в). Очевидно, что в антисимметрическом графе нет петель.

В качестве примера можно рассмотреть граф, являющийся моделью некоторой группы людей: вершины графа интерпретируют людей, а дуги – их взаимоотношения. Так, если в графе дуга, нарисованная от вершины х_i к вершине х_j , означает, что х_i является другом или родственником х_j , тогда данный граф должен быть симметрическим. Если дуга, направленная от х_i к х_j , означает, что вершина х_j подчинена вершине х_i , то такой граф должен быть антисимметрическим.