Теорема де Моргана
| Теорема (де Моргана): |
| Доказательство: |
|
Докажем первое утверждение, второе доказывается аналогично. Сначала докажем, что . Пусть . Значит, такого, что . Следовательно, . Теперь докажем, что Пусть . Тогда . Поскольку не входит ни в одно объединяемое множество, то Аналогично, в силу выбора выполняется искомое включение. |
Теорема де Моргана устанавливает двойственность понятий объединения и пересечения множеств. То есть, имея некоторое верное равенство, содержащее объединения и пересечения, можно переписать его, заменив пересечения на объединения и наоборот. Например, из равенства
Действия над множествами. Диаграммы Венна
Диаграммы Венна (по аналогии с кругами Эйлера) – это схематическое изображение действий с множествами. Опять же предупреждаю, что я рассмотрю не все операции:
1) Пересечение множеств характеризуется логической связкой И и обозначается значком
Пересечением множеств и называется множество , каждый элемент которого принадлежит и множеству , и множеству . Грубо говоря, пересечение – это общая часть множеств:
Так, например, для множеств :
Если у множеств нет одинаковых элементов, то их пересечение пусто. Такой пример нам только что встретился при рассмотрении числовых множеств:
Множества рациональных и иррациональных чисел можно схематически изобразить двумя непересекающимися кругами.
Операция пересечения применима и для бОльшего количества множеств, в частности в Википедии есть хороший .
2) Объединение множеств характеризуется логической связкой ИЛИ и обозначается значком
Объединением множеств и называется множество , каждый элемент которого принадлежит множеству или множеству :
Запишем объединение множеств : – грубо говоря, тут нужно перечислить все элементы множеств и , причём одинаковые элементы (в данном случае единица на пересечении множеств) следует указать один раз.
Но множества, разумеется, могут и не пересекаться, как это имеет место быть с рациональными и иррациональными числами:
В этом случае можно изобразить два непересекающихся заштрихованных круга.
Операция объединения применима и для бОльшего количества множеств, например, если , то:
, при этом числа вовсе не обязательно располагать в порядке возрастания (это я сделал исключительно из эстетических соображений). Не мудрствуя лукаво, результат можно записать и так:
3) Разностью множеств и называют множество , каждый элемент которого принадлежит множеству и не принадлежит множеству :
Разность читаются следующим образом: «а без бэ». И рассуждать можно точно так же: рассмотрим множества . Чтобы записать разность , нужно из множества «выбросить» все элементы, которые есть во множестве :
Пример с числовыми множествами: – здесь из множества целых чисел исключены все натуральные, да и сама запись так и читается: «множество целых чисел без множества натуральных».
Зеркально: разностью множеств и называют множество , каждый элемент которого принадлежит множеству и не принадлежит множеству :
Для тех же множеств – из множества «выброшено» то, что есть во множестве .
А вот эта разность оказывается пуста: . И в самом деле – если из множества натуральных чисел исключить целые числа, то, собственно, ничего и не останется 
Кроме того, иногда рассматривают симметрическую разность , которая объединяет оба «полумесяца»: – иными словами, это «всё, кроме пересечения множеств».
4) Декартовым (прямым) произведением множеств и называется множество всех упорядоченных пар , в которых элемент , а элемент
Запишем декартово произведение множеств :
– перечисление пар удобно осуществлять по следующему алгоритму: «сначала к 1-му элементу множества последовательно присоединяем каждый элемент множества , затем ко 2-му элементу множества присоединяем каждый элемент множества , затем к 3-му элементу множества присоединяем каждый элемент множества »:
Зеркально: декартовым произведением множеств и называется множество всех упорядоченных пар , в которых . В нашем примере:
– здесь схема записи аналогична: сначала к «минус единице» последовательно присоединяем все элементы множества , затем к «дэ» – те же самые элементы:
Но это чисто для удобства – и в том, и в другом случае пары можно перечислить в каком угодно порядке – здесь важно записать все возможные пары. А теперь гвоздь программы: декартово произведение – это есть не что иное, как множество точек нашей родной декартовой системы координат
А теперь гвоздь программы: декартово произведение – это есть не что иное, как множество точек нашей родной декартовой системы координат .
Задание для самостоятельного закрепления материала:
Выполнить операции 
, если:
1) ;
2)
Множество удобно расписать перечислением его элементов.
И пунктик с промежутками действительных чисел:
3)
Напоминаю, что квадратная скобка означает включение числа в промежуток, а круглая – его невключение, то есть «минус единица» принадлежит множеству , а «тройка» не принадлежит множеству . Постарайтесь разобраться, что представляет собой декартово произведение данных множеств. Если возникнут затруднения, выполните чертёж 
Краткое решение задачи в конце урока.
Отношения между множествами
Два множества и могут вступать друг с другом в различные отношения.
Включение
A включено в B, если каждый элемент множества A принадлежит также и множеству B :
\displaystyle A\subseteq B\Leftrightarrow \forall a\in A \ \colon \ a\in B
A включает B, если B включено в A:
{\displaystyle A\supseteq B\Leftrightarrow B\subseteq A}
A строго включено в B, если A включено в B, но не равно ему:
{\displaystyle A\subset B\Leftrightarrow (A\subseteq B)\land (A\neq B)}
Равенство
A равно B, если A и B включены друг в друга:
{\displaystyle A=B\Leftrightarrow (A\subseteq B)\land (B\subseteq A)}
Общие элементы
A и B не пересекаются, если у них нет общих элементов:
A и B не пересекаются {\displaystyle \Leftrightarrow \forall a\in A \ \colon a\notin B}
Понятие множества. Способы задания множеств.
Данная тема содержит немало терминологии, поэтому я добавлю содержание темы, которое позволит легче ориентироваться в материале.
Начнём с того, что же, собственно, понимать под словом «множество». На интуитивном уровне под множеством понимают некую совокупность объектов, именуемых элементами множества. Например, можно говорить о множестве груш на столе, множестве букв в слове «множество» и так далее. Георг Кантор (немецкий математик, основатель современной теории множеств) писал, что под «множеством я понимаю вообще всё то многое, которое возможно мыслить как единое, т.е. такую совокупность определённых элементов, которая посредством одного закона может быть соединена в одно целое». Некоторое время понятие множества, введённое Кантором, полагалось довольно очевидным и не требующим дополнительных пояснений. Казалось, что появление работ Больцано, а затем и Кантора в конце 19 — начале 20 века, положит конец многим вопросам (например, окончательно разрешит апории Зенона, разрешит проблему бесконечности и т.д.) и станет началом новой математики. Гениальный немецкий математик Давид Гильберт отмечал, что «Никто не изгонит нас из рая, созданного Кантором».
1.1.2. Способы задания множеств
Множество считается заданным, если о каждом элементе можно однозначно сказать, принадлежит он этому множеству или нет.
А) Простейший способ задания множества состоит просто в перечислении всех элементов данного множества.
Если множество A конечное, состоящее из элементов A1, A2, …, AN, то пишут A = A1, A2, …, AN> . В частности, A> — множество, состоящее из одного элемента A.
Но такой способ задания применим, разумеется, лишь к конечным множествам.
Б) Другой, универсальный способ: задание множества A С помощью характеристического свойства элементов данного множества, то есть такого свойства, которым обладают все элементы множества A и не обладают другие элементы, не принадлежащие A.
Если P(X) — такое свойство, то пишут:
Например, для конечного множества A = A1, A2,…, AN> можно записать: A = X | x = A1, или X = a2, или …, или X = AN>. Множество всех депутатов парламента можно задать тьак: D = X | X — депутат>. Множество всех студентов S = x | X — студент>.
В) Еще один способ — это задание множества с помощью порождающей процедуры, или алгоритмический способ.
Например, пусть M = — множество степеней числа 2. Тогда его можно задать так:
1)
Другой пример: множество МP = задается как последовательность троек подряд идущих цифр десятилетней записи числа p = 3,141592653589793238462… . (В действительности, учитывая трансцендентность числа p, множество МP содержит все целые числа от 0 до 999.)
Г) Четвертый способ — задание множеств с помощью операций над уже известными множествами.
К описанию свойств, задающих множество, естественно предъявить требования точности и недвусмысленности. Например, множество хороших фильмов 1999г. разные люди зададут разными списками. Даже сами критерии отбора фильмов могут оказаться различными.
Надежный способ точного описания множества — распознающая (разрешающая) процедура. Например, для множества степеней двойки М2N разрешающей процедурой может служить разложение числа на простые множители.
Задание множества М4 нельзя отнести ни к одному из перечисленных способов; оно по сути совсем не задано, а только названо. Задать его можно списком футболистов, или описанием: М4 есть множество лиц, имеющих удостоверение футболиста клуба «Динамо-Минск». В этом случае разрешающая процедура — это проверка документов.
Источник
Обозначение множеств, подмножеств и их элементов
Чаще всего множества обозначаются латинскими буквами- $A, B, C , D, X, Y, Z, W$ и Т.Д.
Элементы множеств обозначаются строчными буквами $a,b,c,d,x,y,z$ и Т.Д.
Записать принадлежность некоторого элемента к некоторому множеству, например то, что некоторой элемент $a$ будет входить в множество $A$ математически можно так: $a\in A$.Прочитать данную запись можно так: a принадлежит множеству $A$.
Если же некоторый элемент, например, $b$ не принадлежит множеству $B$, то это записывается так: $b\notin B$.Читают эту запись так: $b$ не принадлежит множеству $B$
Например, если обозначить множество целых чисел за $A$, что тогда можно записать: $3\in A$, $7,5\notin B$
Пустое множество в математике обозначают так: $ᴓ$
Для обозначения того, что множество $B$ является подмножеством множества $A$, используют обозначение: Знак $\subset $ обозначает включение одного множества в другое множество.
Пример 1
Определить какие элементы из перечисленных $12,38,54,79,934$ будут входить в множество $A$- чисел кратных $3$.
Решение: По условию множество $A$ содержит в себе элементы, каждый из которых должен быть кратным, т.е. делится без остатка на $3.$ Значит для того чтобы определить будут ли заданные числа являться элементами множества $A$ нам надо проверить какие из них будут делится на $3$ без остатка, какие нет.
Вспомним признак делимости на $3$: Если сумма цифр, входящих в состав числа делится на $3$, то число делится на $3$ без остатка.
$12$ делится на $3$, т.к. сумма цифр числа $12$ равна $3$
число $38$ на $3$ без остатка делится не будет, т.к. сумма цифр $3+8=11$ не делится на $3$ без остатка
аналогично т.к. суммы цифр числа $54$ равна $9$ доказываем, что на $3$ оно делится, в число $74$ на $3$ делится не будет, т.к. сумма цифр равна $11.$
Найдем сумму цифр числа $934: 9+3+4=16$, число $16$ не кратно $3$ ,значит и число $934$ на $3$ без остатка делится не будет
Теперь сделаем вывод, какие числа будут являться элементами множества $A$:
\
Отображение множеств
Отображение множества во множество – это правило, по которому каждому элементу множества ставится в соответствие элемент (или элементы) множества . В том случае если в соответствие ставится единственный элемент, то данное правило называется однозначно определённой функцией или просто функцией.
Функцию, как многие знают, чаще всего обозначают буквой – она ставит в соответствие каждому элементу единственное значение , принадлежащее множеству .
Ну а сейчас я снова побеспокою множество студентов 1-го ряда и предложу им 6 тем для рефератов (множество ):
Векторы Матрицы Определители Комплексные числа (о, да!) Теория пределов Что такое производная?
Установленное (добровольно или принудительно =)) правило ставит в соответствие каждому студенту множества единственную тему реферата множества .
…а вы, наверное, и представить себе не могли, что сыграете роль аргумента функции =) =)
Элементы множества образуют область определения функции (обозначается через ), а элементы множества – область значений функции (обозначается через ).
Построенное отображение множеств имеет очень важную характеристику: оно является взаимно-однозначным или биективным (биекцией). В данном примере это означает, что каждому студенту поставлена в соответствие одна уникальная тема реферата, и обратно – за каждой темой реферата закреплён один и только один студент.
Однако не следует думать, что всякое отображение биективно. Если на 1-й ряд (к множеству ) добавить 7-го студента, то взаимно-однозначное соответствие пропадёт – либо один из студентов останется без темы (отображения не будет вообще), либо какая-то тема достанется сразу двум студентам. Обратная ситуация: если к множеству добавить седьмую тему, то взаимнооднозначность отображения тоже будет утрачена – одна из тем останется невостребованной.
Уважаемые студенты на 1-м ряду, не расстраивайтесь – остальные 20 человек после пар пойдут прибирать территорию университета от осенней листвы. Завхоз выдаст двадцать голиков, после чего будет установлено взаимно-однозначное соответствие между основной частью группы и мётлами…, а Вольдемар ещё и в магазин сбегать успеет =)
Теперь разберёмся со «школьной» функцией одной переменной. Пожалуйста, загляните на страницу Функции и графики (отроется на соседней вкладке), и в Примере 1 найдите график линейной функции .
Задумаемся, что это такое? Это правило , которое каждому элементу области определения (в данном случае это все значения «икс») ставит в соответствие единственное значение . С теоретико-множественной точки зрения, здесь происходит отображение множества действительных чисел во множество действительных чисел:
Первое множество мы по-обывательски называем «иксами» (независимая переменная или аргумент), а второе – «игреками» (зависимая переменная или функция).
Далее взглянем на старую знакомую параболу . Здесь правило каждому значению «икс» ставит в соответствие его квадрат, и имеет место отображение:
Итак, что же такое функция одной переменной? Функция одной переменной – это правило , которое каждому значению независимой переменной из области определения ставит в соответствие одно и только одно значение .
Как уже отмечалось в примере со студентами, не всякая функция является взаимно-однозначной. Так, например, у функции каждому «иксу» области определения соответствует свой уникальный «игрек», и наоборот – по любому значению «игрек» мы сможем однозначно восстановить «икс». Таким образом, это биективная функция.
! На всякий случай ликвидирую возможное недопонимание: моя постоянная оговорка об области определения не случайна! Функция может быть определена далеко не при всех «икс», и, кроме того, может быть взаимно-однозначной и в этом случае. Типичный пример:
А вот у квадратичной функции не наблюдается ничего подобного, во-первых: – то есть, различные значения «икс» отобразились в одно и то же значение «игрек»; и во-вторых: если кто-то вычислил значение функции и сообщил нам, что , то не понятно – этот «игрек» получен при или при ? Что и говорить, взаимной однозначностью здесь даже не пахнет.
Задание 2: просмотреть графики основных элементарных функций и выписать на листок биективные функции. Список для сверки в конце этого урока.
Способы задания множеств.
Первый способ – это простое перечисление элементов множества. Естественно, такой способ подходит лишь для конечных множеств. Например, с помощью данного способа множество первых трёх натуральных чисел будет записано так:
Часто в литературе можно встретить обозначения такого характера: $T=\$. Здесь множество задаётся не перечислением элементов, как кажется на первый взгляд. Перечислить все чётные неотрицательные числа, которые и составляют множество $T$, невозможно, ибо этих чисел бесконечно много. Запись вида $T=\$ допускается только тогда, когда не вызывает разночтений.
Второй способ – задать множество с помощью так называемого характеристического условия (характеристического предиката) $P(x)$. В этом случае множество записывается в таком виде:
Запись $\$ читается так: «множество всех элементов $x$, для которых высказывание $P(x)$ истинно». Что именно значит словосочетание «характеристическое условие» проще пояснить на примере. Рассмотрим такое высказывание:
$$P(x)=»x\; – \;натуральное\; число,\; последняя\; цифра\; которого \;равна\; 7″$$
Подставим в это высказывание вместо $x$ число 27. Мы получим:
$$P(27)=»27\; – \;натуральное\; число,\; последняя\; цифра\; которого \;равна\; 7″$$
Это истинное высказывание, так как 27 действительно является натуральным числом, последняя цифра которого равна 7. Подставим в это высказывание число $\frac$:
$$P\left(\frac\right)=»\frac\; – \;натуральное\; число,\; последняя\; цифра\; которого \;равна\; 7″$$
Это высказывание ложно, так как $\frac$ не является натуральным числом. Итак, для некоторых объектов $x$ высказывание $P(x)$ может быть ложно, для некоторых – истинно (а для некоторых вообще не определено). Нас будут интересовать лишь те объекты, для которых высказывание $P(x)$ будет истинно. Именно эти объекты и образуют множество, заданное с помощью характеристического условия $P(x)$ (см. пример №3).
Третий способ – задать множество с помощью так называемой порождающей процедуры. Порождающая процедура описывает, как получить элементы множества из уже известных элементов или неких иных объектов (см. пример №4).
Записать множество $A=\$ перечислением элементов.
Множество $A$ теперь задано с помощью перечисления элементов.
Описать элементы множества $M$, которое задано такой порождающей процедурой:
- $3\in M$;
- Если элемент $x\in M$, то $3x\in M$.
- Множество $M$ – является подмножеством любого множества $A$, удовлетворяющего условиям №1 и №2.
Давайте пока оставим в покое условие №3 и посмотрим, какие элементы входят в множество $M$. Число 3 туда входит согласно первому пункту. Так как $3\in M$, то согласно пункту №2 имеем: $3\cdot 3\in M$, т.е. $9\in M$. Так как $9\in M$, то согласно пункту №2 получим: $3\cdot 9\in M$, т.е. $27\in M$. Так как $27\in M$, то по тому же пункту №2 имеем: $81\in M$. Короче говоря, построенное множество 3, 9, 27, 81 и так далее – это натуральные степени числа 3.
$$3^1=1; \; 3^2=9; \; 3^3=27; \; 3^4=81;\; \ldots$$
Итак, кажется, что искомое множество задано. И выглядит оно так: $\$. Однако действительно ли условия №1 и №2 определяют только это множество?
Рассмотрим множество всех натуральных чисел, т.е. $N$. Число 3 – натуральное, посему $3\in N$. Вывод: множество $N$ удовлетворяет пункту №1. Далее, для любого натурального числа $x$ множество $N$ содержит также и число $3x$. Например, 5 и 15, 7 и 21, 13 и 39 и так далее. Значит, множество $N$ удовлетворяет условию №2. И, кстати сказать, не только множество $N$ удовлетворяет условиям №1 и №2. Например, множество всех нечётных натуральных чисел $N_1=\$ тоже подходит под условия пунктов №1 и №2. Как же указать, что нам нужно именно множество $\$?
Вот тут на помощь приходит пункт №3. Говоря огрублённо, он означает, что множество $M$ – наименьшее из всех возможных множеств. Так как множества $N$ и $\$ удовлетворяют пунктам №1 и №2, но $N\nsubseteq \$, то множество $N$ не удовлетворяет третьему пункту. Аналогично, так как $N_1\nsubseteq \$, то множество $N_1$ также не удовлетворяет пункту №3. Можно показать (если это необходимо, отпишите мне на почту, я распишу подробнее), что всем трём пунктам удовлетворяет лишь множество $\$, т.е.
Обычно при задании множества с помощью таких правил (которые часто называют рекурсивными или индуктивными) третий пункт подразумевается, но не оговаривается явно. Но нужно иметь его в виду.
Заметили ошибку, опечатку, или некорректно отобразилась формула? Отпишите, пожалуйста, об этом в данной теме на форуме (регистрация не требуется).
Источник