Два множества A и B равны, если они состоят из одних и тех же элементов.

Из этого принципа следует, что для любых двух различных множеств всегда найдется некоторый объект, являющийся элементом одного из них и не являющийся элементом другого. Так как пустые совокупности не содержат элементов, то они не различимы и поэтому пустое множество – единственно.

Подмножества. Определение равенства множеств можно сформулировать иначе, используя понятие подмножества.

Определение. Множество A называется подмножеством множества B , если каждый элемент A является элементом B.

Следствие 1. Очевидно,
для любого множества A, т.к. каждый элемент из A есть элемент из A.

Следствие 2. Для любого множества A,
, ибо если бы пустое множество не являлось подмножеством A, то в пустом подмножестве существовали бы элементы, не принадлежащие A. Однако пустое множество не содержит вообще ни одного элемента.

Если
, то пишут
, и если
, то A – собственное подмножество B.

Понятие подмножества множеств позволяет легко формализовать понятие равенства двух множеств.

Утверждение. Для любых A и B

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

Замечание . Отношение включения  обладает рядом очевидных свойств:

(рефлексивность);

(транзитивность).

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

Пример. Пусть
– это множество, состоящее из трех элементов. Тогда булеанℬ (X) это множество:

Собственными подмножествами ℬ (X) являются следующие множества:

{a},{b},{c},{a,b},{b,c},{a,c}.

В общем случае, если множество X содержит n элементов, то множество его подмножеств ℬ (X) состоит из элементов.

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

Пусть U – универсальное множество,
. Тогда для множеств X,Y можно определить операции
.

Определение . Объединением множеств X и Y называется множество
, состоящее из элементов, входящих хотя бы в одно из множеств (X или Y):

Рис. 1.1 – Объединение множеств Рис. 1.2 – Пересечение множеств

Определение . Пересечением множеств X и Y называется множество
, состоящее из элементов, входящих в X и в Y одновременно:

Определение . Разностью множеств X и Y называется множество
, состоящее из элементов, входящих в множество X, но не входящих в Y:

Рис. 1.3 – Разность множеств
Рис. 1.4 – Симметрическая

разность множеств

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

Определение . Для любого множества
дополнением множествадо U называется такое множество, что:

Рис. 1.5 – Дополнение множества X до U

На рис. 1.1  1.5 представлены диаграммы Венна, наглядно демонстрирующие результаты операций
.

Дополнение множества иногда обозначается
. Операции
связаны между собой законами де Моргана:

, (1.7)

. (1.8)

В справедливости законов де Моргана легко убедиться самостоятельно.

В таблице 1.1 представлены основные свойства операций над множествами.

Таблица 1.1

	Свойства операций	Объединение, пересечение, дополнение
	коммутативность	,
	ассоциативность
	дистрибутивность
	идемпотентность	, , , , ,
	теоремы де Моргана	,
	инволюция

Операции объединения и пересечения можно обобщить. Пусть
– множество индексов,
– семейство подмножеств множества X.

Определение. Семейство подмножеств
множества X, для которых
, называетсяразбиением множества X, если выполняются следующие два условия:

,

Определение. Семейство подмножеств
множества X называетсяпокрытием множества X, если:
.

Определение. Класс K подмножеств из U называется алгеброй, если:

1.
;

2. из того, что
следует, что
;

3. из того, что
следует, что
.

Пример. Пусть
, тогда класс
образует алгебру.

Определение. Класс F подмножеств из U образует -алгебру, если:

1.
;

2. из того, что
следует
;

3. из того, что
,
следует, что
.

Пример. Множество всех подмножеств U образует -алгебру, т.е.ℬ (U) – -алгебра.

В математике понятие множества является одним из основных, фундаментальным, однако единого определения множества не существует. Одним из наиболее устоявшихся определений множества является следующее: под множеством понимают любое собрание определённых и отличных друг от друга объектов, мыслимых как единое целое. Создатель теории множеств немецкий математик Георг Кантор (1845-1918) говорил так: "Множество есть многое, мыслимое нами как целое".

Ели ли Вы сегодня обед? Сейчас станет известна страшная тайна. Обед является множеством. А именно, множеством блюд, из которых он состоит. В нём (как правило) нет одинаковых блюд, и во множестве все элементы должны быть разными. А, если на обед у Вас был тот же самый салат, что и на завтрак, то этот салат является пересечением множеств "Обед" и "Завтрак".

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

А улица, на которой Вы живёте? Она является собранием многих разных объектов, но обязательно есть множество домов, расположенных на этой улице. Поэтому множество домов является подмножеством множества "Улица".

Итак, мы рассмотрели не только примеры множеств, но и пример операции над множествами - пересечение, а также отношение включения подмножества во множество. Все эти понятия будем рассматривать подробно на этом уроке.

Но пока ещё один пример практического рассмотрения множеств.

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

Пример 0 (Паскаль). Существует набор продуктов, продаваемых в нескольких магазинах города. Определить: какие продукты есть во всех магазинах города; полный набор продуктов в городе.

Решение. Определяем базовый тип данных Food (продукты), он может принимать значения, соответствующие названиями продуктов (например, hleb). Объявляем тип множества, он определяет все подмножества, составленные из комбинаций значений базового типа, то есть Food (продукты). И формируем подмножества: магазины "Солнышко", "Ветерок", "Огонёк", а также производные подмножества: MinFood (продукты, которые есть во всех магазинах), MaxFood (полный набор продуктов в городе). Далее прописываем операции для получения производных подмножеств. Подмножество MinFood получается в результате пересечения подмножеств Solnyshko, Veterok и Ogonyok и включает те и только те элементы этих подмножеств, которые включены в каждое их этих подмножеств (в Паскале операция пересечения множеств обозначается звёздочкой: A * B * C, математическое обозначение пересечения множеств дано далее). Подмножество MaxFood получается в результате объединения тех же подмножеств и включает элементы, которые включены во все подмножества (в Паскале операция объединения множеств обозначается знаком "плюс": A + B + C, математическое обозначение объединения множеств дано далее).

Код PASCAL

Program Shops; type Food=(hleb, moloko, myaso, syr, sol, sahar, maslo, ryba); Shop = set of Food; var Solnyshko, Veterok, Ogonyok, MinFood, MaxFood: Shop; Begin Solnyshko:=; Veterok:=; Ogonyok:=; ... MinFood:=Solnyshko * Veterok * Ogonyok; MaxFood:=Solnyshko + Veterok + Ogonyok; End.

Какие бывают множества

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

Натуральных чисел 0, 1, 2, 3, 4, ...

Простых чисел

Чётных целых чисел

и т.п. (основные числовые множества рассмотрены в этого материала).

Объекты, составляющие множество, называются его элементами. Можно сказать, что множество - это "мешок с элементами". Очень важно: в множестве не бывает одинаковых элементов.

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

Если M - множество, а a - его элемент, то пишут: a ∈M , что означает "a принадлежит множеству M ".

Из первого (нулевого) примера на Паскале с продуктами, которые есть в тех или иных магазинах:

hleb ∈VETEROK ,

что означает: элемент "hleb" принадлежит множеству продуктов, которые есть в магазине "VETEROK".

Существуют два основных способа задания множеств: перечисление и описание.

Множество можно задать, перечислив все его элементы, например:

VETEROK = {hleb , syr , maslo } ,

A = {7 , 14 , 28 } .

Перечислением можно задать только конечное множество. Хотя можно сделать это и описанием. Но бесконечные множества можно задать только описанием.

Для описания множеств используется следующий способ. Пусть p (x ) - некоторое высказывание, которое описывает свойства переменной x , областью значений которых является множество M . Тогда через M = {x | p (x )} обозначаентся множество, состоящее из всех тех и только тех элементов, для которых высказывание p (x ) истинно. Это выражение читается так: "Множество M , состоящее из всех таких x , что p (x ) ".

Например, запись

M = {x | x ² - 3x + 2 = 0}

Пример 6. Согласно опросу 100 покупателей рынка, купивших цитрусовые, апельсины купили 29 покупателей, лимоны - 30 покупателей, мандарины - 9, только мандарины - 1, апельсины и лимоны - 10, лимоны и мандарины - 4, все три вида фруктов - 3 покупателя. Сколько покупателей не купили ни одного вида перечисленных здесь цитрусовых? Сколько покупателей купили только лимоны?

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

Для определения ещё одной важной операции над множествами - декартова произведения множеств введём понятие упорядоченного набора длины n .

Длиной набора называется число n его компонент. Набор, составленный из элементов , взятых именно в этом порядке, обозначается . При этом i я () компонента набора есть .

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

Декартовым (прямым) произведением множеств называется множество, обозначаемое и состоящее из всех тех и только тех наборов длины n , i -я компонента которых принадлежит .

«Под множеством мы понимаем объединение в одно целое определенных, вполне различимых объектов нашей интуиции или нашей мысли» - так описал понятие «множество» Георг Кантор, основатель теории множеств.
Основные предпосылки канторовской теории множеств сводятся к следующему:
1° Множество может состоять из любых различимых объектов.
2° Множество однозначно определяется набором составляющих его объектов.
3° Любое свойство определяет множество объектов, которые этим свойством обладают.

Если х - объект, Р - свойство, Р(х) - обозначение того, что х обладает свойством Р, то через {х|Р(х)} обозначают весь класс объектов, обладающих свойством Р. Объекты, составляющие класс или множество, называют элементами класса или множества.

Термин «множество » употребляется как синоним понятий совокупность, собрание, коллекция некоторых элементов. Так, можно говорить о:
а) множестве пчёл в улье,
б) множестве точек отрезка,
в) множестве вершин квадрата или о множествах его сторон и диагоналей,
г) множестве студентов в аудитории и т.д.
В приведённых примерах в случаях а), в)-г) соответствующие множества состоят из определённого конечного числа предметов, такие множества называются конечными . Множество точек отрезка (пример б)) пересчитать невозможно, поэтому такие множества называются бесконечными . Множество, не содержащее ни одного элемента, называется пустым множеством.

Наиболее простая форма задания множества — перечисление его элементов, например А={4, 7, 13} (множество А состоит из трёх элементов — целых чисел 4, 7, 13). Другая часто применяемая форма задания — указание свойств элементов множества, например A = {x| x^2 ≤ 4} — множество чисел х, удовлетворяющих указанному условию.

Множества обычно обозначаются большими буквами А, В, С,…., а их элементы — малыми: а, в, с,… Запись а ∈ А (читается: а принадлежит А) или A ∋ a (читается: А содержит а) означает, что а есть элемент множества А. Пустое множество обозначается значком Ø.

Если каждый элемент множества В является также элементом множества А, множество В называется подмножеством множества А (обозначение — B ⊆ A или A ⊇ B).

Каждое множество является своим подмножеством (это самое «широкое» подмножество множества). Пустое множество является подмножеством любого множества (это самое «узкое» подмножество). Любое другое подмножество множества А содержит хотя бы один элемент множества А, но не все его элементы. Такие подмножества называются истинными, или собственными подмножествами. Для истинных подмножеств множества А применяется обозначение B ⊂ A или A ⊃ B. Если одновременно B ⊆ A и A ⊆ B, т.е каждый элемент множества В принадлежит А, и в то же время каждый элемент А принадлежит В, то А и В, очевидно, состоят из одних и тех же элементов и, следовательно, совпадают. В этом случае применяется знак равенства множеств: A = B. (Символы ∈, ∋, ⊂, ⊃, ⊆, ⊇ называются символами включения).

Геометрически множества обычно изображаются как некоторые множества точек плоскости. В любой имеющей смысл задаче обычно рассматриваются подмножества некоторого «наибольшего» множества U, которое называют универсальным множеством. Так, на рис. 1 изображено универсальное множество U и два его подмножества — множества А и В, B ⊂ A. Сами картинки типа рис. 1 называются диаграммами Эйлера-Венна .

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

Пример 1. Дано множество А = {а, с, р, о}. Выпишите все подмножества
данного множества.
Решение:

Собственные подмножества: {а} , {с} , {р} , {о} , {а, с} , {а, р} , {а, о}, {с, р} , {с, о } ∈, {р, о}, {а, с,р} , {а, с, о}, {с, р, о}.

Несобственные: {а, с, р, о}, Ø.

Всего: 16 подмножеств.

Пояснение. Множество A является подмножеством множества B если каждый элемент множества A содержится также в B.

Пустое множество ∅ является подмножеством любого множества, называется несобственным;
. любое множество является подмножеством самого себя, также называется несобственным;
. У любого n-элементного множества ровно 2 n подмножеств.

Последнее утверждение является формулой для нахождения числа всех подмножеств без перечисления каждого.

Вывод формулы: Допустим у нас имеется множество из n-элементов. При составлении подмножеств первый элемент может принадлежать подмножеству или не принадлежать, т.е. первый элемент можем выбрать двумя способами, аналогично для всех остальных элементов (всего n-элементов), каждый можем выбрать двумя способами, и по правилу умножения получаем: 2∙2∙2∙ ...∙2=2 n

Для математиков сформулируем теорему и приведем строгое доказательство.

Теорема. Число подмножеств конечного множества, состоящего из n элементов, равно 2 n .

Доказательство. Множество, состоящее из одного элемента a, имеет два (т.е. 2 1) подмножества: ∅ и {a}. Множество, состоящее из двух элементов a и b, имеет четыре (т.е. 2 2) подмножества: ∅, {a}, {b}, {a; b}.
Множество, состоящее из трех элементов a, b, c, имеет восемь (т.е. 2 3) подмножеств:
∅, {a}, {b}, {b; a}, {c}, {c; a},{c; b}, {c; b; a}.
Можно предположить, что добавление нового элемента удваивает число подмножеств.
Завершим доказательство применением метода математической индукции. Сущность этого метода в том, что если утверждение (свойство) справедливо для некоторого начального натурального числа n 0 и если из предположения, что оно справедливо для произвольного натурального n = k ≥ n 0 можно доказать его справедливость для числа k + 1, то это свойство справедливо для всех натуральных чисел.

1. Для n = 1 (база индукции) (и даже для n = 2, 3) теорема доказана.

2. Допустим, что теорема доказана для n = k, т.е. число подмножеств множества, состоящего из k элементов, равно 2 k .

3. Докажем, что число подмножеств множества B, состоящего из n = k + 1 элемента равно 2 k+1 .
Выбираем некоторый элемент b множества B. Рассмотрим множество A = B \ {b}. Оно содержит k элементов. Все подмножества множества A - это подмножества множества B, не содержащие элемент b и, по предположению, их 2 k штук. Подмножеств множества B, содержащих элемент b, столько же, т.е. 2 k
штук.

Следовательно, всех подмножеств множества B: 2 k + 2 k = 2 ⋅ 2 k = 2 k+1 штук.
Теорема доказана.

В примере 1 множество А = {а, с, р, о} состоит из четырех элементов, n=4, следовательно, число всех подмножеств равно 2 4 =16.

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

Пример 2. Eсть множество {a b c}, в соответствие ставятся следующие числа:
000 = {0} (пустое множество)
001 = {c}
010 = {b}
011 = {b c}
100 = {a}
101 = {a c}
110 = {a b}
111 = {a b c}

Калькулятор множества всех подмножеств.

В калькуляторе уже набраны элементы множества А = {а, с, р, о} , достаточно нажать кнопку Submit. Если вам необходимо решение своей задачи, то набираем элементы множества на латинице, через запятую, как показано в примере.

Сравнительный анализ возможностей человека и машины

Показатели превосходства человека	Показатели превосходства машины
Обнаружение полезных сигналов с низким энергетическим уровнем (световых, звуковых)	Выполнение однообразных точных работ длительное время.
Опознание образов и их обобщение	Быстрая реакция на сигналы управления
Обнаружение сигналов на фоне высоких уровней шумов	Плавное и точное приложение больших усилий.
Хранение большого объема информации длительное время и использование требуемой информации в нужное время	Хранение больших объемов информации и быстродействие при их вводе
Способность к восприятию и использованию неполной информации	Выполнение сложных вычислений с большой точностью и скоростью
Нахождение и использование эвристических методов решения	Одновременное выполнение нескольких разнообразных действий
Реагирование на непредвиденные обстоятельства	Использование дедуктивных методов в процессе принятия решения
Оригинальность в решении задач	Нечувствительность ко многим посторонним факторам
Способность учитывать прошлый опыт и изменять способ действий	Работоспособность в условиях, где человек не может работать
Способность выполнять операции в непредвиденных ситуациях	Чувствительность к стимулам превосходящим человеческие
Способность работать в условиях перегрузок	Время стабильной работы больше, чем у человека
Чувствительность к широкому диапазону стимулов

В системе «человек-машина» к человеку предъявляются ряд требований.

Человек должен:

Уметь четко формулировать задачи;

Знать компоненты СОУ и ее возможности;

Уметь составлять программу решения задачи;

Уметь сравнивать полученный результат с предполагаемым и изменять несоответствие изменением способа решения задачи.

Множество - это объединение в одно целое объектов, связанных между собой неким свойством. Термин «множество» в математике не всегда обозначает большое количество предметов, оно может состоять из одного элемента и вообще не содержать элементов, тогда его называют пустым и обозначают .

Множество B называется подмножеством множества A , если любой элемент множества B является элементом множества A . Обозначение: .

Пример. . Запишем все подмножества множества M: {-14}, {11}, {17}, {-14;11}, {-14;17}, {11;17}, {-14;11;11}, .

Свойства включения множеств:

1. Пустое множество является подмножеством любого множества: Æ Ì А .

2. Любое множество является подмножеством самого себя, т. е. для любого множества А справедливо включение А Ì А .

3. Если А – подмножество множества В , а В – подмножество множества С , то А – подмножество множества С .

Универсальное множество – это самое большее множество, содержащее в себе все множества, рассматриваемые в данной задаче.

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