Тема 2. Множества

План:

1.            Общие понятия теории множеств.

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

3.            Кортежи

4.            Декартово произведение множеств

5.            Соответствия между множествами.

6.            Отображения

7.            Бинарные отношения

8.            Элементы комбинаторики

9.            Подстановки

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

Теоретические сведения

1. Общие понятия теории множеств.

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

Под множеством можно понимать - неупорядоченную совокупность элементов, набор объектов.

Примерами множеств может служить:

1.    Множество людей.  Группа детей одного класса – элементами служат учащиеся именно данного класса. Множество берез в лесу

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

3.  Множество натуральных чисел  Натуральные числа – числа от 1 до бесконечности.

4.  Множество треугольников – любой треугольник является элементом этого класса.

5.  Знаки препинания, буквы алфавита, цифры для записи чисел 

6.  D= {2, 4, 6, 8, 10, 12…} – множество четных чисел

7.  V= {3, 6, 9, 12…} – множество чисел кратных трем

8.  M={Иванов, Петров, Сидоров…} – множество спортсменов

9.  Множество делителей числа 24.

10.Множество письменных принадлежностей

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

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

Принадлежность  элемента а множеству А обозначается символом Î, например, а Î А (от греческой буквы e), не принадлежность символом Ï.

Например: Х={1,2,3,4,5,6}. 

3ÎХ –  число 3 принадлежит множеству Х. 9ÏX  - число 9 не принадлежит множеству Х.

Совокупность {1,2,3,4,5,6} является множеством, последовательность (порядок) записи элементов не имеет значения, поэтому оно неотличимо от множества {1, 3, 5, 2, 4, 6}

Совокупность {1,2,3,1,3,3,5} множеством не является, здесь некоторые элементы записаны не единичным образом.

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

В последнем случае элементы сами являются множествами.

Число элементов множества А обозначается как |А| и называется мощностью или численность  А (размером, нормой, длиной и др.) множества.

Множество, не содержащее элементов, обозначаемое символом Æ  и называемое пустым множеством. Пустое множество может встретиться в реальных задачах. Так, например, может оказаться, что множество студентов группы, получивших две неудовлетворительные оценки, пусто. Это значит, что таковых студентов нет. Пустым множеством может оказать множество корней уравнения или решения неравенства. В программировании понятие пустого множества встречается очень часто.

Множество может быть представлено (задано) в виде:

~    Перечисления, например, А= {a, b, c, d, e, f};

~    Свойства, например,  В={b_i ½b_i  - студенты старше 25 лет};

~    Процедуры, например,  C={c_i | c_i =n², n Î N}.

              Здесь и далее при задании множества символ | - вертикальная разделительная черта, используется вместо слов "таких, что", "всех" и др.

  Рассмотрим запись  M={x | P(x)}. Она означает, что множество M состоит их всех элементов x, обладающие свойством  P(x).

Например, M={x | 3x² -2x =0}. Множеству M принадлежат корни уравнения 3x² -2x =0. Это числа 0 и 1,5. M= {0; 1,5}

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

  &, Ç  для обозначения союза "И"

  È  для обозначения союза "ИЛИ"

  " квантор общности, для обозначения слов: "для всех", "для каждого"...

  $ квантор существования, для обозначения слов: "существует","найдется" ….

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

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

Для наглядности множества на плоскости  изображаются кругами или иными плоскими геометрическими фигурами, замкнутыми контрами, которые называются по фамилиям двух математиков, работавших в теории множеств,  кругами Эйлера – Венна

Элементы, принадлежащие множеству, изображаются точками внутри фигуры.

Множества:  А и В считаются равными, если они состоят из одних и тех же элементов. С помощью выше указанных символов Этот факт можно записать следующим образом:

Если ("а ÎА $b ÎВ, а=b) Ç ( "b ÎВ $aÎА, а=b).

Подмножеством некоторого множества называется любое множество, состоящее из элементов данного множества. Говорят, что подмножество является частью множества. На рисунке изображено  множество А, которое является подмножеством множества В. Данный факт принято обозначать символами: А Ì В.  

Если множество X есть подмножество множества Y, то пишут XÌY. Знак Ì называется знаком включения. Не следует его путать со знаком Î - принадлежности.

Если подмножество совпадает с самим данным множеством  или является пустым множеством, то оно называется несобственным подмножеством. Все остальные подмножества называются собственными подмножествами. 

Число всех подмножеств множества,  содержащего n элементов, вычисляется по формуле k=2ⁿ.  Сюда входят все  собственные и несобственные подмножества. Множество всех подмножеств данного множества называется Булеаном

Множество В называется дополнением множества А если ни один элемент из В не принадлежит А. Дополнение обозначается как: В =`А;  В =A'; иногда B= -A

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

Рассмотрим множество двузначных чисел:

А={10;11;12;…98;99}

В={10;20;30;40;50;50:70;80;90} – двузначные числа, оканчивающиеся нулем, являются подмножеством множества двузначных чисел.

C- {11; 12…} - двузначные числа, не оканчивающиеся нулем, которые и будут являться дополнением подмножества В до множества А

Если некоторое множество D дополняется до некоторого другого множества R, то такое множество R называется универсальным множеством.  Предполагается, что дополнение происходит до некоторого универсального множества, определяемого предметной областью задачи. Универсальное множество часто  обозначается символом U. Любое множество является подмножеством универсального множества. Например:

1. Для множества натуральных чисел универсальным множество можно считать множество действительных чисел.

2.  Для множества детей человеческого общества, универсальным множеством является множество всех людей.

3. Для множества студентов конкретных групп, универсальным множеством является множество студентов факультета.

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

Задание 1.

Что можно сказать о множествах:

Y={1;2;3;4;5;7;8;9}- множество однозначных чисел

Х={2;4;6;8} – множество четных однозначных чисел

Ответ:

1.              n(Y)=9, n(X)=4

2.              XÌY

3.              Z={1;3;5;7;9} – дополнение множества X до Y.

4.     Универсальным множеством для множества Y есть множество, например, двузначных чисел.

  5.    и т.д.

Задание 2. Изобразите геометрически (кругами) множества

D= {10, 11, 12 …98, 99} – множество двузначных натуральных чисел,

F= {10, 20… 90} - множество чисел, оканчивающихся нулем.

Решение.  См. рисунок.

Очевидно, что все элементы множества  F – принадлежат множеству .D. В таких случаях говорят, что множество  F – есть подмножество множества D

Подмножества могут содержать по одному, по два, по три  и более элементов.

Число возможных подмножеств, которое можно составить из данного множества, вычисляется по формуле:

  k=2ⁿ, где n – число элементов в заданном множестве